Welcome to: A crash course on using machine learning methods effectively in practice

Supervised learning

Unsupervised learning

  • data is unlabelled and is denoted via \(\mathcal{D}=\{x^{(1)},\ldots,x^{(n)}\}\)

Clustering using Kmeans

  • Clustering allows to identify meaningful groups, or clusters, among the data points and find representative centers of these clusters.

  • Samples within each cluster are more closely related to one another than samples from different clusters.

  • Clustering is the act of associating a cluster \(\ell\) with each observation, where \(\ell\) comes from a small finite set, \(\{1,\ldots,K\}\).

  • Clustering algorithm works on the data \(\mathcal{D}\) and outputs a function \(c(\cdot)\) which maps individual data points to the label values \(\{1,\ldots,K\}\).

  • K-means algorithm is one very basic, yet powerful heuristic algorithm.

  • With K-means, we pre-specify a number \(K\), determining the number of clusters.

  • \(K\) may be treated as a hyper-parameter.

  • The algorithm seeks the function \(c(\cdot)\), or alternatively the partition \(C_1,\ldots,C_K\), it also seeks representative centers (also known as centroids), of the clusters, denoted by \(J_1,\ldots,J_K\), each an element of \({\mathbb R}^p\).

  • Ideal aim of \(K-means\) is to minimization,

\[\begin{equation} \label{eq:kMeansObj} \text{Clustering cost} = \sum_{\ell = 1}^K \sum_{x \in C_\ell} || x- J_\ell ||^2. \end{equation}\]

  • Generally computationally intractable since it requires considering all possible partitions of \(\mathcal{D}\) into clusters.

  • Can be approximately minimized via the K-means algorithm using a classic iterative approach.

  • The K-means algorithm: two sub-tasks called mean computation, and labelling.

  • Mean computation: Given \(c(\cdot)\), or a clustering \(C_1,\ldots,C_K\), find \(J_1,\ldots,J_K\) that minimizes \[\begin{equation} \label{eq:meanComp} J_\ell = \frac{1}{|C_\ell|} \sum_{x \in C_\ell} x, \qquad \text{for} \qquad \ell= 1,\ldots,K. \end{equation}\]

  • Labelling: Given, \(J_1,\ldots,J_K\), \(c(\cdot)\) is defined as \[\begin{equation} \label{eq:labelStep} c(x) = \textrm{argmin}_{\ell \in \{1,\ldots,K\}} ~||x -J_\ell ||. \end{equation}\]

  • The label of each element is determined by the closest center in Euclidean space.

Kmeans in action

library(animation)
set.seed(101)
library(mvtnorm)
x = rbind(rmvnorm(40, mean=c(0,1),sigma = 0.05*diag(2)),rmvnorm(40, mean=c(0.5,0),sigma = 0.05*diag(2)),rmvnorm(40, mean=c(1,1),sigma = 0.05*diag(2)))
par(mfrow=c(3,2))
colnames(x) = c("x1", "x2")
kmeans.ani(x, centers = matrix(c(0.5,1,0.5,0,1,1),byrow=T,ncol=2))

Image Segmentation with K-means

  • The goal of image segmentation is to label each pixel of an image with a unique class from a finite number of classes.

unsupervised image segmentation via K-means clustering

  • Each pixel of the image is considered a point in \(\mathcal{D}\) and the dimension of each point is typically \(p=3\) (red, green, and blue) for color images.

  • Can produce impressive image segmentation without any other information except for the image.

  • Example: color image is a \(n = 640\times 640=409,600\) pixel color image (\(p=3\)).

  • Run K-means algorithm which groups similar pixels based on their attributes and assigns the attributes of the corresponding cluster center to the pixel in the image.

Your TURN

  • Use your own image.
library(ggplot2)
library(jpeg)
img <- readJPEG("Yoni-ben-pool-seg.jpg")

# Obtain the dimension
imgDm <- dim(img)

# Assign RGB channels to data frame
imgRGB <- data.frame(
  x = rep(1:imgDm[2], each = imgDm[1]),
  y = rep(imgDm[1]:1, imgDm[2]),
  R = as.vector(img[,,1]),
  G = as.vector(img[,,2]),
  B = as.vector(img[,,3])
)

par(mfrow=c(3,1))

# Plot the original image
p1 <- ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = rgb(imgRGB[c("R", "G", "B")])) +
  labs(title = "Original Image") +
  xlab("x") +
  ylab("y") 
p1


kClusters <- 2
kMeans <- kmeans(imgRGB[, c("R", "G", "B")], centers = kClusters)
kColours <- rgb(kMeans$centers[kMeans$cluster,])


p2 <- ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = kColours) +
  labs(title = paste("k-Means Clustering of", kClusters, "Colours")) +
  xlab("x") +
  ylab("y") 
p2

kClusters <- 6
kMeans <- kmeans(imgRGB[, c("R", "G", "B")], centers = kClusters)
kColours <- rgb(kMeans$centers[kMeans$cluster,])


p6 <- ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = kColours) +
  labs(title = paste("k-Means Clustering of", kClusters, "Colours")) +
  xlab("x") +
  ylab("y") 
p6

Principal Component Analysis

  • Not all \(p\) dimensions of the data are equally useful.
  • Especially the case in the presence of high dimensional data. (large \(p\)).
  • Many features may be either completely redundant or uninformative.
  • These cases are referred to as correlated features or noise features
  • PCA is a well-known and widely used dimensionality reduction technique for a wide variety of applications such as data compression, feature extraction, and visualization.
  • Basic idea of PCA is to project each point of \(\mathcal{D}\) which has many correlated coordinates onto fewer coordinates called principal components which are uncorrelated.

  • This is done while still retaining most of the variability present in the data.

  • PCA offers a low-dimensional representation of the features that attempts to capture the most important information from the data.

  • As input, PCA uses the de-meaned data from the centered data matrix \(X\)

\[\begin{equation} X=\begin{bmatrix} \vert & &\vert \\ x_{(1)} &\dots &x_{(p)} \\ \vert & & \vert \end{bmatrix} \quad \textrm{with} \quad x_{(i)}=\begin{bmatrix} x_i^{(1)} \\ \vdots \\ x_i^{(n)} \end{bmatrix} \end{equation}\]

  • PCA uses a linear combination of these columns to arrive at the vectors of the new features \(\tilde{x}_{(1)},\ldots,\tilde{x}_{(m)}\).

\[ \tilde{x}_{(i)} = v_{i,1} \begin{bmatrix} \vert \\ x_{(1)} \\ \vert \end{bmatrix} + v_{i,2} \begin{bmatrix} \vert \\ x_{(2)} \\ \vert \end{bmatrix} + ~ \ldots ~ + v_{i,p} \begin{bmatrix} \vert \\ x_{(p)} \\ \vert \end{bmatrix} \quad \text{for} \quad i=1,\ldots,m, \]

  • each new \(n\) dimensional vector, \(\tilde{x}_{(i)}\), is a linear combination of the original features.

  • \(\tilde{x}_{(i)} = X v_i\) where \(v_i = (v_{i,1},\ldots,v_{i,p})\) is called the loading vector for \(i\)

\[\begin{equation} \label{eq:pca-mat} \underbrace{\begin{bmatrix} \vert & &\vert \\ \tilde{x}_{(1)} & \dots \hspace{-0.3cm}&\tilde{x}_{(m)} \\ \vert & & \vert \end{bmatrix}}_{\underset{\textrm{Reduced data}}{\widetilde{X}_{n\times m}}} = \underbrace{ \begin{bmatrix} \vert & & &\vert \\ x_{(1)} & \dots &\dots &x_{(p)} \\ \vert & && \vert \end{bmatrix} }_{\underset{\text{Original de-meaned data}}{X_{n\times p}}}\times \underbrace{ \begin{bmatrix} \vert & &\vert \\ \vert & &\vert \\ v_1 & \dots \hspace{-0.3cm}&v_m \\ \vert & &\vert \\ \vert & & \vert \end{bmatrix}}_{\underset{\textrm{Matrix of loading vectors}}{\widetilde{V}_{p\times m}}}. \end{equation}\]

PCA on Wisconsin breast cancer data

  • Wisconsin breast cancer data: \(p=30\) and \(n=569\).

  • Aim to visualize this data using PCA we set \(m=2\)

load("Breast_cancer.RData")
head(Breast_cancer_data[,c(1:6)])
data <- Breast_cancer_data
dim(data)
[1] 569  32
library(FactoMineR)
Registered S3 method overwritten by 'htmlwidgets':
  method           from         
  print.htmlwidget tools:rstudio
library(ggplot2)
library(dplyr)

pca <- PCA(data[,-c(1,2)],ncp=2,graph=FALSE)
dat <- data.frame(data,pc1=pca$ind$coord[,1],pc2=pca$ind$coord[,2],diagnosis=as.factor(data[,2]))

#dat <- dat %>% filter(pc1<7 & pc2<10) 

p1 <- ggplot(data = dat, aes(x = pc1, y = pc2))+
  geom_hline(yintercept = 0, lty = 2) +
  geom_vline(xintercept = 0, lty = 2) +
  geom_point(alpha = 0.8,size=2.5) + theme_bw()
 
p1 + theme(axis.text = element_text(size = 20))+ theme(axis.title = element_text(size = 20))   

  • Variance explained by the first two components
pca$eig[1:2,]
       eigenvalue percentage of variance cumulative percentage of variance
comp 1  13.281608               44.27203                          44.27203
comp 2   5.691355               18.97118                          63.24321
  • Color the points based on the labels benign vs. malignant, a useful pattern emerges ?
p2 <- ggplot(data = dat, aes(x = pc1, y = pc2, color = diagnosis))+
  geom_hline(yintercept = 0, lty = 2) +
  geom_vline(xintercept = 0, lty = 2) +
  geom_point(alpha = 0.8,size=2.5) + theme_bw()+
  theme(legend.position=c(0.15,0.85),legend.title=element_blank())
Warning: A numeric `legend.position` argument in `theme()` was deprecated in ggplot2 3.5.0.
Please use the `legend.position.inside` argument of `theme()` instead.
p3 <- p2 +  scale_color_discrete( labels = c("benign", "malignant"))

p3 + theme(legend.text=element_text(size=20),axis.text = element_text(size = 20))+ theme(axis.title = element_text(size = 20))

Derivation of PCA

  • The PCA framework tries to project the data in the directions with maximum variance.

  • Since \(\tilde{x}_{(i)}=Xv_i\) we can formulate this by maximizing the sample variance of the components of \(\tilde{x}_{(i)}\).

  • \(\tilde{x}_{(i)}\) is a \(0\) mean vector, its sample variance is \(\tilde{x}_{(i)}^\top \tilde{x}_{(i)}/n\).

  • We have, \[ \text{Sample variance of component}~i = \frac{1}{n} v_i^\top X^\top X v_i = v_i^\top S v_i, \] where \(S\) is the sample covariance of the data.

  • It turns out the a very useful way to represent the loading vectors \(v_1,\ldots,v_m\) is by normed eigenvectors associated with eigenvalues of the sample covariance matrix \(S\)

  • \(S\) is symmetric and positive semi-definite, the eigenvalues of \(S\) are real and non-negative, a fact which allows us to order them via \(\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_p \ge 0\).

  • We then pick the loading vector \(v_i\) to be a normed eigenvector associated with \(\lambda_i\), namely,

\[\begin{equation} \label{eq:eig-pca} S v_i = \lambda_i v_i, \end{equation}\]

  • The first loading vector is associated with the highest eigenvalue; the second is associated with the second highest eigenvalue; and so fourth. The symmetry of \(S\) also means that its eigenvectors are orthogonal and hence \(\widetilde{V}\) is a matrix with orthonormal columns.

PCA Through SVD

  • Any \(n \times p\) dimensional matrix \(X\) of rank \(r\) can be represented as

\[\begin{equation} \label{eq:reduced-svd} X=U \Delta V^\top=\sum_{i=1}^{r} \delta_{i} \, u_{i} \, v_{i}^\top, \quad \text{with} \quad \Delta=\textrm{diag}(\delta_1,\ldots,\delta_r), \quad \text{and} \quad \delta_i > 0. \end{equation}\]

  • \(n \times r\) matrix \(U\) and the \(p \times r\) matrix \(V\) are both with orthonormal columns denoted \(u_i\) and \(v_i\) respectively for \(i=1,\ldots,r\).

  • Columns are called the left and right singular vectors respectively.

  • \(\delta_i\) in the \(r \times r\) diagonal matrix \(\Delta\) are called singular values and are ordered as \(\delta_1 \geq \delta_2 \geq \cdots \geq \delta_r>0\).

  • SVD representation of the sample covariance: \[ S = \frac{1}{n} \underbrace{V\Delta^\top U^\top}_{X^{\top}}\underbrace{U\Delta V^\top}_{X} = \frac{1}{n} V \Delta^2 V^\top, \quad \text{with} \quad \Delta^2=\textrm{diag}(\delta_1^2,\ldots,\delta_r^2). \]

Here the fact that \(U\) has orthonormal columns implies \(U^\top U\) is the \(r\times r\) identity matrix and hence it cancels out:

\[\begin{equation} \label{eq:S-svd} S = \sum_{i=1}^r \frac{\delta_i^2}{n} \, v_i \, v_i^\top. \end{equation}\]

  • Compare to the eigenvector based representation of PCA:

  • Using the Spectral decomposition of \(S\) \[\begin{equation} \label{eq:S-spectral} S = \widetilde{V}^\top \Lambda \widetilde{V} = \sum_{i=1}^r \lambda_i \,v_i \, v_i^\top. \end{equation}\]

  • Thus, \(\lambda_i=\delta^2_i/n\) and the loading vectors in spectral decomposition are the right singular vectors in SVD: \(\widetilde{V} = V\).

  • Further, to obtain the data matrix of principal components, \(\widetilde{X}\) we set \(\widetilde{X} = X V\). Using the SVD, PCA can be represented:

\[\begin{equation} \label{eq:pca-svd-relationship} \widetilde{X} = \underbrace{~\, U \Delta V^\top}_{X} V = U \Delta = \begin{bmatrix} \vert & \vert & &\vert \\ \delta_1 u_1 & \delta_2 u_2 \hspace{-0.3cm} & \dots \hspace{-0.3cm}& \delta_r u_r \\ \vert & \vert & & \vert \end{bmatrix}. \end{equation}\]

  • Each column of the reduced data matrix \(\widetilde{X}\) is a left singular vector \(u_i\) stretched by the singular value \(\delta_i\).

SVD for Compression

  • The singular value decomposition can also be viewed as a means for compressing any matrix \(X\).

  • A rank \(m<r\) approximation of \(X\) is,

\[\begin{equation} \label{eq:svd-approx} \widehat{X} = \sum_{i=1}^{m} \delta_{i} \, u_{i} \, v_{i}^\top \approx X, \qquad \text{where} \qquad X- \widehat{X} = \sum_{i={m+1}}^{r} \delta_{i} \, u_{i} \, v_{i}^\top. \end{equation}\]

  • The rank of \(\widehat{X}\) is \(m\) and since one often uses \(m\) significantly smaller than \(r\), this is called a low rank approximation.

  • For small enough \(\delta_{m+1}\) the approximation error is negligible since the summation of rank one matrices \(\delta_{i} \, u_{i} \, v_{i}^\top\) for \(i=m+1,\ldots,r\) is small.

  • The number of values used in this representation of \(\widehat{X}\) is \(m\times (1+ n + p)\) and for small \(m\) this number is generally much smaller than \(n \times p\) which is the number of values in \(X\).

  • Hence this may viewed as a compression method.

SVD in action for compression

  • We seek to have the best rank \(m\) approximation in terms of minimization of \(\|X-\widehat{X}\|_F\).

  • Frobenious norm noted \(\| A \|_F\): square root of the sum of the squared elements of the matrix \(A\)

  • Low rank approximations established by Eckart–Young-Mirsky theorem.

\[\begin{equation} \label{eq:ek-yng} \underset{\widehat{X}\text{ of rank }m}{\min}\left\|X - \widehat{X}\right\|^2_F= \left\| X - \sum_{i=1}^ m\delta_i \, u_i v_i^{\top}\right\|^2_F = \sum_{i=m+1}^{r}\delta_i^2. \end{equation}\]

  • consider a simple visual example with a \(353 \times 469\) monochrome (grayscale) image appearing this is \(X\).

  • The original image uses \(353\times 469=165,557\) values while the \(m=50\) approximation only uses \(50 \times (1+353+469) = 41,150\) values. That is the approximation yields \(\widehat{X}\) which is compressed to about \(25\%\) of the size of \(X\) and looks very similar.

Your Turn

  • Adapt the code using your own image
if (!"jpeg" %in% installed.packages()) install.packages("jpeg")
# Read image file into an array with three channels (Red-Green-Blue, RGB)
myImage <- jpeg::readJPEG("CODE_WORKSHOP/pool_graysacle.jpg")

r <- myImage[, , 1] 
# Performs full SVD 
myImage.r.svd <- svd(r)# ; lmyImage.g.svd <- svd(g) ; myImage.b.svd <- svd(b)
rgb.svds <- list(myImage.r.svd)#



plot.image <- function(pic, main = "") {
  h <- dim(pic)[1] ; w <- dim(pic)[2]
  plot(x = c(0, h), y = c(0, w), type = "n", xlab = "", ylab = "", main = main)
  rasterImage(pic, 0, 0, h, w)
}


compress.image <- function(rgb.svds, nb.comp) {
  # nb.comp (number of components) should be less than min(dim(img[,,1])), 
  # i.e., 170 here
  svd.lower.dim <- lapply(rgb.svds, function(i) list(d = i$d[1:nb.comp], 
                                                     u = i$u[, 1:nb.comp], 
                                                     v = i$v[, 1:nb.comp]))
  img <- sapply(svd.lower.dim, function(i) {
    img.compressed <- i$u %*% diag(i$d) %*% t(i$v)
  }, simplify = 'array')
  img[img < 0] <- 0
  img[img > 1] <- 1
  return(list(img = img, svd.reduced = svd.lower.dim))
}



par(mfrow = c(2, 2))
plot.image(r, "Original image")

p <- 10 ; plot.image(compress.image(rgb.svds, p)$img[,,1], 
                     paste("SVD with", p, "components"))

p <- 30 ; plot.image(compress.image(rgb.svds, p)$img[,,1], 
                     paste("SVD with", p, "components"))


p <- 50 ; plot.image(compress.image(rgb.svds, p)$img[,,1], 
                     paste("SVD with", p, "components"))

A taste of Shallow Autoencoders

  • A schematic of an autoencoder with a single hidden layer.

  • The input \(x \in \Re^p\) is transformed into a bottleneck, also called the code which is some \(\tilde{x} \in \Re^m\) and is the hidden layer of the model.

  • Then the bottleneck is further transformed into the output \(\hat{x} \in \Re^p\).

  • The part of the autoencoder that transforms the input into the bottleneck is called the encoder and the part of the autoencoder that transforms the bottleneck to the output is called the decoder. Both the encoder and the decoder have parameters that are to be learned.

  • Interestingly for input \(x\), once parameters are trained, we generally expect the autoencoder to generate output \(\hat{x}\) that is as similar to the input \(x\) as possible.

  • Consider the activity of data reduction where the dimension of the bottleneck \(m\) is significantly smaller than the input and output dimension \(p\)

  • For example, return to the case of MNIST digits where \(p=784\). For our example here, assume we have an auto encoder with \(m=30\).

  • A trained autoencoder yields \(x \approx \hat{x}\) then it means that we have an immediate data reduction method.

  • With the trained encoder we are able to convert digit images, each of size \(28 \times 28 = 784\), into much smaller vectors, each of size \(30\).

  • With the trained decoder we are able to convert back and get an approximation of the original image. This choice of \(m\) implies a rather remarkable compression factor of about \(26\).

Autoencoder loss

  • The most straightforward choice for the distance penalty in \(C_i(\theta)\) is the square of the Euclidean distance:

\[\begin{equation} \label{eq:autoencoder-loss} C_i(\theta) = \| x^{(i)} - f_\theta(x^{(i)}) \|^2 \quad \text{and thus} \quad C(\theta \, ; \, \mathcal D) = \frac{1}{n} \sum_{i=1}^n \| x^{(i)} - f_\theta(x^{(i)}) \|^2. \end{equation}\]

With this loss structure, learning the parameters, \(\theta\), of an autoencoder based on data \(\mathcal D\) is the process of minimizing \(C(\theta \, ; \, \mathcal D\).

  • Decompose \(f_\theta(\cdot)\) to be a composition of the encoder function denoted via \(f^{[1]}_{\theta^{[1]}}(\cdot)\) and the decoder function denoted via \(f^{[2]}_{\theta^{[2]}}(\cdot)\):

\[ \hat{x} = f_\theta(x) = \big(f^{[2]}_{\theta^{[2]}} \circ f^{[1]}_{\theta^{[1]}}\big) (x) = f^{[2]}_{\theta^{[2]}}\big( f^{[1]}_{\theta^{[1]}}(x) \big), \]

  • We define,

\[\begin{equation} \label{eq:encoder-decoder} \begin{array}{rcl} f^{[1]}_{\theta^{[1]}}(u)&=&S^{[1]}(b^{[1]} + W^{[1]} u) \quad \text{for} \quad u \in \Re^p \qquad (\textrm{Encoder})\\ f^{[2]}_{\theta^{[2]}}(u)&=&S^{[2]}(b^{[2]} + W^{[2]} u) \quad \text{for} \quad u \in \Re^m \qquad (\textrm{Decoder}), \end{array} \end{equation}\]

  • The encoder parameters \(\theta^{[1]}\) are composed of the bias \(b^{[1]}\in \Re^{m}\) and weight matrix \(W^{[1]}\in \Re^{m \times p}\)

  • The decoder parameters \(\theta^{[2]}\) are composed of the bias \(b^{[2]}\in \Re^{p}\) and weight matrix \(W^{[2]}\in \Re^{p \times m}\).

\[\begin{equation} \label{eq:compete-2layer-auto-theta} \theta = (b^{[1]},W^{[1]},b^{[2]},W^{[2]}). \end{equation}\]

  • Vector activation functions \(S^{[1]}(\cdot)\) and \(S^{[2]}(\cdot)\): we construct these based on scalar activation functions \(\sigma^{[\ell]}: \Re \to \Re\) for \(\ell=1,2\).

  • Specifically, we set \(S^{[\ell]}(z)\) to be the element wise application of \(\sigma^{[\ell]}(\cdot)\) on each of the coordinates of \(z\)

\[\begin{equation} \label{eqn:activation-function-vector} S^{[\ell]}(z)=\left[ \begin{matrix} \sigma^{[\ell]}\left(z_{1}\right) \\ \vdots\\ \sigma^{[\ell]}\left(z_{r}\right) \end{matrix} \right]. \end{equation}\]

  • The loss function representation as,

\[\begin{equation} \label{eq:costautoencoder} C(\theta \, ; \,\mathcal D)=\frac{1}{n} \sum_{i=1}^n\ \|x^{(i)}-\underbrace{S^{[2]}(W^{[2]}S^{[1]}(W^{[1]}x^{(i)}+b^{[1]})+b^{[2]})}_{f_{\theta}(x^{(i)})}\|^2. \end{equation}\]

  • With this loss function, for given data \(\mathcal D\), the learned autoencoder parameters \(\hat{\theta}\) are given by a solution to the optimization problem \(\text{min}_\theta C(\theta \, ; \,\mathcal D)\).

PCA is an Autoencoder

  • Autoencoders generalize principal component analysis (PCA)

  • PCA is essentially a shallow auto-encoder with identity activation functions \(\sigma^{[\ell]}(u) = u\) for \(\ell=1,2\), also known as a linear autoencoder.

  • PCA yields one possible solution to the learning optimization problem for linear autoencoders.

Autoencoder on MNIST

  • consider using an autoencoder on MNIST where \(p=28\times28 = 784\) and we use \(m=2\).

  • We encode this via PCA, a shallow non-linear autoencoder, and a deep autoendoer that has hidden layers.

  • The autoencoders are trained on the training set and the codes presented are both for the training set, and for the testing set data.

  • We color the code points based on the labels. This allows us to see how different labels are generally encoded onto different regions of the code space.

  • One application of such data reduction is to help separate the data

  • It is evident that as model complexity increases better separation occurs in the data.

  • In terms of reconstruction, it is also evident in this case that more complex models exhibit better reconstruction ability.

A denoising autoencoder

  • This model learns to remove noise during the reconstruction step for noisy input data.

  • It takes in partially corrupted input and learns to recover the original denoised input.

  • It relies on the hypothesis that high-level representations are relatively stable and robust to entry corruption and that the model is able to extract characteristics that are useful for the representation of the input distribution.

Your turn

Interpolation on the latent space

  • Take \(x^{(i)}\) and \(x^{(j)}\) from \(\mathcal D = \{x^{(1)},\ldots,x^{(n)}\}\) and consider the convex combination \[ x_\lambda^{\text{naive}} = \lambda x^{(i)} + (1-\lambda) x^{(j)}, \] for some \(\lambda \in [0,1]\).

  • \(x_\lambda^{\text{naive}}\) is a weighted average between the two observations.

  • \(\lambda\) captures which of the observations has more weight.

  • Such arithmetic on the associated feature vectors is too naive and often meaningless.

  • When considering the latent space representation of the images it is often possible to create a much more meaningful interpolation between the images.

  • Train an autoencoder and then encode \(x^{(i)}\) and \(x^{(j)}\) to obtain \(\tilde{x}^{(i)}\) and \(\tilde{x}^{(j)}\).

  • Then interpolate on the codes, and finally decode \(\tilde{x}_\lambda\) to obtain an interpolated image.

\[ {x}_\lambda^{\text{encoder}} = f^{[2]} \Big(\lambda f^{[1]}({x}^{(i)}) + (1-\lambda) f^{[1]}({x}^{(j)}) \Big). \]

  • one potential application of such interpolation is for design purposes, say in art or architecture, where one chooses two samples as a starting point and then uses interpolation to see other samples lying ``in between’’.

Ruta R package for autoencoder

The following coge will take some times to run

# To install the R package downlaod the tar.gz file at https://cran.r-project.org/src/contrib/Archive/ruta/
library(ruta)
library(rARPACK)
library(ggplot2)
###############
### Function plot 
###############
plot_digit <- function(digit, ...) {
  image(keras::array_reshape(digit, c(28, 28), "F")[, 28:1], xaxt = "n", yaxt = "n", col=gray(1:256 / 256), ...)
}

plot_sample <- function(digits_test, model1,model2,model3, sample) {
  sample_size <- length(sample)
  layout(
    matrix(c(1:sample_size, (sample_size + 1):(4 * sample_size)), byrow = F, nrow = 4)
  )
  
  
  for (i in sample) {
    par(mar = c(0,0,0,0) + 1)
    plot_digit(digits_test[i, ])
    plot_digit(model1[i, ])
    plot_digit(model2[i, ])
    plot_digit(model3[i, ])
  }
}


#######################
#### Load MNIST DATA
#######################

mnist = keras::dataset_mnist()

# Normalization to the [0, 1] interval
x_train <- keras::array_reshape(
  mnist$train$x, c(dim(mnist$train$x)[1], 784)
)
x_train <- x_train / 255.0
x_test <- keras::array_reshape(
  mnist$test$x, c(dim(mnist$test$x)[1], 784)
)
x_test <- x_test / 255.0

if(T){
network <- input() + dense(30, "tanh") + output("sigmoid")
network1 <- input() + dense(50, "tanh") +dense(10, "linear")+dense(50, "tanh") +output("sigmoid")
}

### model simple
network.simple <- autoencoder(network)#, loss = "binary_crossentropy")
model = train(network.simple, x_train, epochs = 10)
decoded.simple <- reconstruct(model, x_test)


### model deep
my_ae2 <- autoencoder(network1)#, loss = "binary_crossentropy")
model2 = train(my_ae2, x_train, epochs = 10)
decoded2 <- reconstruct(model2, x_test)

#### Linear interpolation between two digits
digit_A = x_train[which(mnist$train$y==3)[1],]#MNIST digit with 3 (This is the first digit in the train set that has 3)
digit_B = x_train[which(mnist$train$y==3)[10],]#another MNIST digit with 3 (This is the 10[th] digit in the train set that has 3)
latent_A = encode(model2,matrix(digit_A,nrow=1))
latent_B = encode(model2,matrix(digit_B,nrow=1))
lambda = 0.5
latent_interpolation = lambda*latent_A + (1-lambda)*latent_B
rought_interpolation = lambda*digit_A + (1-lambda)*digit_B

output_interpolation = decode(model2,latent_interpolation)


par(mar = c(0,0,0,0) + 1,mfrow=c(1,3))
plot_digit(digit_A)
plot_digit(as.vector(output_interpolation))
plot_digit(digit_B)


par(mar = c(0,0,0,0) + 1,mfrow=c(1,3))
plot_digit(digit_A)
plot_digit(as.vector(rought_interpolation))
plot_digit(digit_B)

Practice and Illustration in Machine Learning

with R code

with Python code

Challenge practice: prediction using PCA

In this challenge, we will use an unsupervised method (Principal Component Analysis) in combination with a supervised method (Sigmoid model) to perform a classification task. This approach reduces data dimensionality to retain the most important information before training a classifier. We will work on the breast cancer dataset. The main steps:

-1. Data Preparation

- Load the dataset and split it into training and testing sets.
- Separate the feature columns from the target variable in both sets.

-2. Dimensionality Reduction with PCA

- Standardize the feature data, then apply PCA to reduce dimensionality.
- Transform both the training and test sets using the trained PCA model.

-3. Model Training

- Train logistic regression models on the PCA-transformed training data
- Use different numbers of principal components.

-4. Model Evaluation

- Evaluate each model on the PCA-transformed test set using accuracy 
- Provide confusion matrices to determine the optimal number of components.
LS0tCnRpdGxlOiAiQSBjcmFzaCBjb3Vyc2Ugb24gdXNpbmcgbWFjaGluZSBsZWFybmluZyBtZXRob2RzIGVmZmVjdGl2ZWx5IGluIHByYWN0aWNlIgpzdWJ0aXRsZTogIlVuc3VwZXJ2aXNlZCBMZWFybmluZyIKYXV0aG9yOiAKICBuYW1lOiBCZW5vaXQgTGlxdWV0IAogIGFmZmlsaWF0aW9uOiBVbml2ZXJzaXR5IE9mIFBhdSBldCBQYXlzIGRlIEwnQWRvdXIKICBoZWFkZXItaW5jbHVkZXM6IFx1c2VwYWNrYWdle2Ftc21hdGh9Cm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIHRoZW1lOiBjZXJ1bGVhbgogICAgaGlnaGxpZ2h0OiBrYXRlCi0tLQoKIAoKYGBge3IsZWNobz1GQUxTRX0KY29sb3JpemUgPC0gZnVuY3Rpb24oeCwgY29sb3IpIHsKICBpZiAoa25pdHI6OmlzX2xhdGV4X291dHB1dCgpKSB7CiAgICBzcHJpbnRmKCJcXHRleHRjb2xvcnslc317JXN9IiwgY29sb3IsIHgpCiAgfSBlbHNlIGlmIChrbml0cjo6aXNfaHRtbF9vdXRwdXQoKSkgewogICAgc3ByaW50ZigiPHNwYW4gc3R5bGU9J2NvbG9yOiAlczsnPiVzPC9zcGFuPiIsIGNvbG9yLAogICAgICB4KQogIH0gZWxzZSB4Cn0KYGBgIAoKV2VsY29tZSB0bzogKipBIGNyYXNoIGNvdXJzZSBvbiB1c2luZyBtYWNoaW5lIGxlYXJuaW5nIG1ldGhvZHMgZWZmZWN0aXZlbHkgaW4gcHJhY3RpY2UqKgoKLSBTb21lIG1hdGVyaWFscyBhbmQgaWxsdXN0cmF0aW9uIGFyZSBiYXNlZCBvbiAqKkNoYXB0ZXIgMioqIGFuZCAqKjMqKiBvZiBbTWF0aGVtYXRpY2FsIEVuZ2luZWVyaW5nIG9mIERlZXAgTGVhcm5pbmddKGh0dHBzOi8vZGVlcGxlYXJuaW5nbWF0aC5vcmcvKQoKLSBEYXRhIGFyZSBhdmFpbGFibGUgYXQgaHR0cHM6Ly9naXRodWIuY29tL2Jlbm9pdC1saXF1ZXQvTUFFREwvCgoKIyBTdXBlcnZpc2VkIGxlYXJuaW5nIAoKIVtdKGZpZ3VyZTJfMV9hX3RyYWluaW5nX3ByZWRpY3Rpb24ucG5nKSAgICAKICAgIAojIFVuc3VwZXJ2aXNlZCBsZWFybmluZyAKIAohW10oZmlndXJlXzJfMV9iX2NsdXN0ZXJpbmdfcmVkdWN0aW9uLnBuZykgCgotIGRhdGEgaXMgdW5sYWJlbGxlZCBhbmQgaXMgZGVub3RlZCB2aWEgJFxtYXRoY2Fse0R9PVx7eF57KDEpfSxcbGRvdHMseF57KG4pfVx9JAoKPHN0eWxlPgpkaXYuYmx1ZSB7IGJhY2tncm91bmQtY29sb3I6I2U2ZjBmZjsgYm9yZGVyLXJhZGl1czogNXB4OyBwYWRkaW5nOiAyMHB4O30KPC9zdHlsZT4KCjxzdHlsZT4KZGl2Lm9yYW5nZSB7IGJhY2tncm91bmQtY29sb3I6I0ZGRDU4MDsgYm9yZGVyLXJhZGl1czogNXB4OyBwYWRkaW5nOiAyMHB4O30KPC9zdHlsZT4KCgojIENsdXN0ZXJpbmcgdXNpbmcgS21lYW5zCgotICoqQ2x1c3RlcmluZyoqIGFsbG93cyB0byBgciBjb2xvcml6ZSgiaWRlbnRpZnkgbWVhbmluZ2Z1bCBncm91cHMiLCJibHVlIilgLCBvciBjbHVzdGVycywgYW1vbmcgdGhlIGRhdGEgcG9pbnRzIGFuZCBmaW5kIHJlcHJlc2VudGF0aXZlIGNlbnRlcnMgb2YgdGhlc2UgY2x1c3RlcnMuIAoKLSBTYW1wbGVzIHdpdGhpbiBlYWNoIGNsdXN0ZXIgYHIgY29sb3JpemUoImFyZSBtb3JlIGNsb3NlbHkiLCJyZWQiKWAgcmVsYXRlZCB0byBvbmUgYW5vdGhlciB0aGFuIHNhbXBsZXMgZnJvbSBkaWZmZXJlbnQgY2x1c3RlcnMuIAoKLSAqKkNsdXN0ZXJpbmcqKiBpcyB0aGUgYWN0IG9mIGFzc29jaWF0aW5nIGEgY2x1c3RlciAkXGVsbCQgd2l0aCBlYWNoIG9ic2VydmF0aW9uLCB3aGVyZSAkXGVsbCQgY29tZXMgZnJvbSBhIHNtYWxsIGZpbml0ZSBzZXQsICRcezEsXGxkb3RzLEtcfSQuCgotIGByIGNvbG9yaXplKCJDbHVzdGVyaW5nIGFsZ29yaXRobSIsInJlZCIpYCB3b3JrcyBvbiB0aGUgZGF0YSAkXG1hdGhjYWx7RH0kIGFuZCBvdXRwdXRzIGEgZnVuY3Rpb24gJGMoXGNkb3QpJCB3aGljaCBtYXBzIGluZGl2aWR1YWwgZGF0YSBwb2ludHMgdG8gdGhlIGxhYmVsIHZhbHVlcyAkXHsxLFxsZG90cyxLXH0kLiAKCi0gYHIgY29sb3JpemUoIkstbWVhbnMiLCJyZWQiKWAgYWxnb3JpdGhtIGlzIG9uZSB2ZXJ5IGJhc2ljLCB5ZXQgcG93ZXJmdWwgaGV1cmlzdGljIGFsZ29yaXRobS4KCi0gV2l0aCAqKkstbWVhbnMqKiwgd2UgcHJlLXNwZWNpZnkgYSBudW1iZXIgJEskLCBkZXRlcm1pbmluZyB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzLiAKCi0gJEskIG1heSBiZSB0cmVhdGVkIGFzIGEgYHIgY29sb3JpemUoImh5cGVyLXBhcmFtZXRlciIsInJlZCIpYC4gCgotIFRoZSBhbGdvcml0aG0gc2Vla3MgdGhlIGZ1bmN0aW9uICRjKFxjZG90KSQsIG9yIGFsdGVybmF0aXZlbHkgdGhlIHBhcnRpdGlvbiAkQ18xLFxsZG90cyxDX0skLCBpdCBhbHNvIHNlZWtzIHJlcHJlc2VudGF0aXZlIGByIGNvbG9yaXplKCJjZW50ZXJzIiwicmVkIilgIChhbHNvIGtub3duIGFzIGByIGNvbG9yaXplKCJjZW50cm9pZHMiLCJyZWQiKWApLCBvZiB0aGUgY2x1c3RlcnMsIGRlbm90ZWQgYnkgJEpfMSxcbGRvdHMsSl9LJCwgZWFjaCBhbiBlbGVtZW50IG9mICR7XG1hdGhiYiBSfV5wJC4gCgo8ZGl2IGNsYXNzID0gImJsdWUiPgotIElkZWFsIGFpbSBvZiAkSy1tZWFucyQgaXMgdG8gIG1pbmltaXphdGlvbiwKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmtNZWFuc09ian0KXHRleHR7Q2x1c3RlcmluZyBjb3N0fSA9IApcc3VtX3tcZWxsID0gMX1eSyBcc3VtX3t4IFxpbiBDX1xlbGx9IHx8IHgtIEpfXGVsbCB8fF4yLgpcZW5ke2VxdWF0aW9ufQo8L2Rpdj4KCi0gR2VuZXJhbGx5IGByIGNvbG9yaXplKCJjb21wdXRhdGlvbmFsbHkgaW50cmFjdGFibGUiLCJyZWQiKWAgc2luY2UgaXQgcmVxdWlyZXMgY29uc2lkZXJpbmcgYWxsIHBvc3NpYmxlIHBhcnRpdGlvbnMgb2YgJFxtYXRoY2Fse0R9JCBpbnRvIGNsdXN0ZXJzLiAKCi0gQ2FuIGJlIGByIGNvbG9yaXplKCJhcHByb3hpbWF0ZWx5IiwiYmx1ZSIpYCBtaW5pbWl6ZWQgdmlhIHRoZSBLLW1lYW5zIGFsZ29yaXRobSB1c2luZyBhIGNsYXNzaWMgaXRlcmF0aXZlIGFwcHJvYWNoLiAKCi0gVGhlIEstbWVhbnMgYWxnb3JpdGhtOiB0d28gc3ViLXRhc2tzIGNhbGxlZCAqKm1lYW4gY29tcHV0YXRpb24qKiwgYW5kICoqbGFiZWxsaW5nKiouIAoKCjxkaXYgY2xhc3MgPSAib3JhbmdlIj4KCi0gKipNZWFuIGNvbXB1dGF0aW9uOioqIEdpdmVuICRjKFxjZG90KSQsIG9yIGEgY2x1c3RlcmluZyAkQ18xLFxsZG90cyxDX0skLCAgZmluZCAkSl8xLFxsZG90cyxKX0skIHRoYXQgbWluaW1pemVzIApcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTptZWFuQ29tcH0KSl9cZWxsID0gXGZyYWN7MX17fENfXGVsbHx9IFxzdW1fe3ggXGluIENfXGVsbH0geCwKXHFxdWFkClx0ZXh0e2Zvcn0gXHFxdWFkIFxlbGw9IDEsXGxkb3RzLEsuClxlbmR7ZXF1YXRpb259CgotICoqTGFiZWxsaW5nOioqIEdpdmVuLCAkSl8xLFxsZG90cyxKX0skLCAgJGMoXGNkb3QpJCBpcyBkZWZpbmVkIGFzClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmxhYmVsU3RlcH0KYyh4KSA9IFx0ZXh0cm17YXJnbWlufV97XGVsbCBcaW4gXHsxLFxsZG90cyxLXH19IH58fHggLUpfXGVsbCB8fC4KXGVuZHtlcXVhdGlvbn0KLSBUaGUgbGFiZWwgb2YgZWFjaCBlbGVtZW50IGlzIGRldGVybWluZWQgYnkgdGhlIGNsb3Nlc3QgY2VudGVyIGluIEV1Y2xpZGVhbiBzcGFjZS4KCjwvZGl2PgoKIyMgS21lYW5zIGluIGFjdGlvbiAKCiFbXSh3b3JrZmxvd2ttZWFucy5wbmcpCmBgYHtyLGZpZy53aWR0aD01LGV2YWw9RkFMU0V9CmxpYnJhcnkoYW5pbWF0aW9uKQpzZXQuc2VlZCgxMDEpCmxpYnJhcnkobXZ0bm9ybSkKeCA9IHJiaW5kKHJtdm5vcm0oNDAsIG1lYW49YygwLDEpLHNpZ21hID0gMC4wNSpkaWFnKDIpKSxybXZub3JtKDQwLCBtZWFuPWMoMC41LDApLHNpZ21hID0gMC4wNSpkaWFnKDIpKSxybXZub3JtKDQwLCBtZWFuPWMoMSwxKSxzaWdtYSA9IDAuMDUqZGlhZygyKSkpCnBhcihtZnJvdz1jKDMsMikpCmNvbG5hbWVzKHgpID0gYygieDEiLCAieDIiKQprbWVhbnMuYW5pKHgsIGNlbnRlcnMgPSBtYXRyaXgoYygwLjUsMSwwLjUsMCwxLDEpLGJ5cm93PVQsbmNvbD0yKSkKYGBgCiAgCiMjIEltYWdlIFNlZ21lbnRhdGlvbiB3aXRoIEstbWVhbnMKCi0gVGhlIGByIGNvbG9yaXplKCJnb2FsIG9mIGltYWdlIHNlZ21lbnRhdGlvbiIsInJlZCIpYCBpcyB0byBgciBjb2xvcml6ZSgibGFiZWwgZWFjaCBwaXhlbCIsImJsdWUiKWAgb2YgYW4gaW1hZ2Ugd2l0aCBhIHVuaXF1ZSBjbGFzcyBmcm9tIGEgZmluaXRlIG51bWJlciBvZiBjbGFzc2VzLiAKCmByIGNvbG9yaXplKCJ1bnN1cGVydmlzZWQgaW1hZ2Ugc2VnbWVudGF0aW9uIiwicmVkIilgIHZpYSAgSy1tZWFucyBjbHVzdGVyaW5nIAoKLSBgciBjb2xvcml6ZSgiRWFjaCBwaXhlbCBvZiB0aGUgaW1hZ2UiLCJibHVlIilgIGlzIGNvbnNpZGVyZWQgYSBwb2ludCBpbiAkXG1hdGhjYWx7RH0kIGFuZCB0aGUgZGltZW5zaW9uIG9mIGVhY2ggcG9pbnQgaXMgdHlwaWNhbGx5ICRwPTMkIChyZWQsIGdyZWVuLCBhbmQgYmx1ZSkgZm9yIGNvbG9yIGltYWdlcy4KCi0gQ2FuIHByb2R1Y2UgX2ltcHJlc3NpdmUgaW1hZ2Ugc2VnbWVudGF0aW9uXyB3aXRob3V0IGFueSBvdGhlciBpbmZvcm1hdGlvbiBleGNlcHQgZm9yIHRoZSBpbWFnZS4gCiAKLSAqKkV4YW1wbGUqKjogY29sb3IgaW1hZ2UgaXMgYSAkbiA9IDY0MFx0aW1lcyA2NDA9NDA5LDYwMCQgcGl4ZWwgY29sb3IgaW1hZ2UgKCRwPTMkKS4gCgotIFJ1biAgSy1tZWFucyBhbGdvcml0aG0gd2hpY2ggZ3JvdXBzIHNpbWlsYXIgcGl4ZWxzIGJhc2VkIG9uIHRoZWlyIGByIGNvbG9yaXplKCJhdHRyaWJ1dGVzIiwiYmx1ZSIpYCBhbmQgYHIgY29sb3JpemUoImFzc2lnbnMiLCJibHVlIilgIHRoZSBhdHRyaWJ1dGVzIG9mIHRoZSBjb3JyZXNwb25kaW5nIGByIGNvbG9yaXplKCJjbHVzdGVyIGNlbnRlciIsInJlZCIpYCB0byB0aGUgcGl4ZWwgaW4gdGhlIGltYWdlLgoKIVtdKFNlZ21lbnRhdGlvbl9rbWVhbnMucG5nKQoKIyMgWW91ciBUVVJOCgotIFVzZSB5b3VyICoqb3duIGltYWdlKiouCgpgYGB7cixldmFsPVRSVUUsY2FjaGU9VFJVRX0KbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGpwZWcpCmltZyA8LSByZWFkSlBFRygiWW9uaS1iZW4tcG9vbC1zZWcuanBnIikKCiMgT2J0YWluIHRoZSBkaW1lbnNpb24KaW1nRG0gPC0gZGltKGltZykKCiMgQXNzaWduIFJHQiBjaGFubmVscyB0byBkYXRhIGZyYW1lCmltZ1JHQiA8LSBkYXRhLmZyYW1lKAogIHggPSByZXAoMTppbWdEbVsyXSwgZWFjaCA9IGltZ0RtWzFdKSwKICB5ID0gcmVwKGltZ0RtWzFdOjEsIGltZ0RtWzJdKSwKICBSID0gYXMudmVjdG9yKGltZ1ssLDFdKSwKICBHID0gYXMudmVjdG9yKGltZ1ssLDJdKSwKICBCID0gYXMudmVjdG9yKGltZ1ssLDNdKQopCgpwYXIobWZyb3c9YygzLDEpKQoKIyBQbG90IHRoZSBvcmlnaW5hbCBpbWFnZQpwMSA8LSBnZ3Bsb3QoZGF0YSA9IGltZ1JHQiwgYWVzKHggPSB4LCB5ID0geSkpICsgCiAgZ2VvbV9wb2ludChjb2xvdXIgPSByZ2IoaW1nUkdCW2MoIlIiLCAiRyIsICJCIildKSkgKwogIGxhYnModGl0bGUgPSAiT3JpZ2luYWwgSW1hZ2UiKSArCiAgeGxhYigieCIpICsKICB5bGFiKCJ5IikgCnAxCgoKa0NsdXN0ZXJzIDwtIDIKa01lYW5zIDwtIGttZWFucyhpbWdSR0JbLCBjKCJSIiwgIkciLCAiQiIpXSwgY2VudGVycyA9IGtDbHVzdGVycykKa0NvbG91cnMgPC0gcmdiKGtNZWFucyRjZW50ZXJzW2tNZWFucyRjbHVzdGVyLF0pCgoKcDIgPC0gZ2dwbG90KGRhdGEgPSBpbWdSR0IsIGFlcyh4ID0geCwgeSA9IHkpKSArIAogIGdlb21fcG9pbnQoY29sb3VyID0ga0NvbG91cnMpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoImstTWVhbnMgQ2x1c3RlcmluZyBvZiIsIGtDbHVzdGVycywgIkNvbG91cnMiKSkgKwogIHhsYWIoIngiKSArCiAgeWxhYigieSIpIApwMgoKa0NsdXN0ZXJzIDwtIDYKa01lYW5zIDwtIGttZWFucyhpbWdSR0JbLCBjKCJSIiwgIkciLCAiQiIpXSwgY2VudGVycyA9IGtDbHVzdGVycykKa0NvbG91cnMgPC0gcmdiKGtNZWFucyRjZW50ZXJzW2tNZWFucyRjbHVzdGVyLF0pCgoKcDYgPC0gZ2dwbG90KGRhdGEgPSBpbWdSR0IsIGFlcyh4ID0geCwgeSA9IHkpKSArIAogIGdlb21fcG9pbnQoY29sb3VyID0ga0NvbG91cnMpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoImstTWVhbnMgQ2x1c3RlcmluZyBvZiIsIGtDbHVzdGVycywgIkNvbG91cnMiKSkgKwogIHhsYWIoIngiKSArCiAgeWxhYigieSIpIApwNgpgYGAKCgojIFByaW5jaXBhbCBDb21wb25lbnQgQW5hbHlzaXMgCgo8ZGl2IGNsYXNzID0gImJsdWUiPgotIE5vdCBhbGwgJHAkIGRpbWVuc2lvbnMgb2YgdGhlIGRhdGEgYHIgY29sb3JpemUoImFyZSBlcXVhbGx5IHVzZWZ1bCIsInJlZCIpYC4gCi0gRXNwZWNpYWxseSB0aGUgY2FzZSBpbiB0aGUgcHJlc2VuY2Ugb2YgYHIgY29sb3JpemUoImhpZ2ggZGltZW5zaW9uYWwgZGF0YSIsInJlZCIpYC4gIChsYXJnZSAkcCQpLiAKLSBNYW55IGZlYXR1cmVzIG1heSBiZSBlaXRoZXIgY29tcGxldGVseSBgciBjb2xvcml6ZSgicmVkdW5kYW50IG9yIHVuaW5mb3JtYXRpdmUiLCJibHVlIilgLgotIFRoZXNlIGNhc2VzIGFyZSByZWZlcnJlZCB0byBhcyBgciBjb2xvcml6ZSgiY29ycmVsYXRlZCBmZWF0dXJlcyIsInJlZCIpYCBvciBgciBjb2xvcml6ZSgibm9pc2UgZmVhdHVyZXMiLCJyZWQiKWAKLSBQQ0EgaXMgYSB3ZWxsLWtub3duIGFuZCB3aWRlbHkgdXNlZCAqKmRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbiB0ZWNobmlxdWUqKiBmb3IgYSAgd2lkZSB2YXJpZXR5IG9mIGFwcGxpY2F0aW9ucyBzdWNoIGFzIGByIGNvbG9yaXplKCJkYXRhIGNvbXByZXNzaW9uIiwiYmx1ZSIpYCwgYHIgY29sb3JpemUoImZlYXR1cmUgZXh0cmFjdGlvbiIsImJsdWUiKWAsIGFuZCBgciBjb2xvcml6ZSgidmlzdWFsaXphdGlvbiIsImJsdWUiKWAuCi0gQmFzaWMgaWRlYSBvZiBQQ0EgaXMgdG8gYHIgY29sb3JpemUoInByb2plY3QiLCJyZWQiKWAgZWFjaCBwb2ludCBvZiAkXG1hdGhjYWx7RH0kIHdoaWNoIGhhcyBtYW55IGNvcnJlbGF0ZWQgY29vcmRpbmF0ZXMgb250byBmZXdlciBjb29yZGluYXRlcyBjYWxsZWQgKipwcmluY2lwYWwgY29tcG9uZW50cyoqIHdoaWNoIGFyZSB1bmNvcnJlbGF0ZWQuIAo8L2Rpdj4KCiFbXShQQ0EuanBnKQoKLSBUaGlzIGlzIGRvbmUgd2hpbGUgc3RpbGwgcmV0YWluaW5nIGByIGNvbG9yaXplKCJtb3N0IG9mIHRoZSB2YXJpYWJpbGl0eSIsInJlZCIpYCBwcmVzZW50IGluIHRoZSBkYXRhLiAKCi0gUENBIG9mZmVycyBgciBjb2xvcml6ZSgiYSBsb3ctZGltZW5zaW9uYWwgcmVwcmVzZW50YXRpb24gb2YgdGhlIGZlYXR1cmVzIiwicmVkIilgIHRoYXQgYXR0ZW1wdHMgdG8gY2FwdHVyZSB0aGUgbW9zdCBpbXBvcnRhbnQgaW5mb3JtYXRpb24gZnJvbSB0aGUgZGF0YS4gCgoKCjxkaXYgY2xhc3MgPSAib3JhbmdlIj4KCi0gIEFzIGlucHV0LCBQQ0EgdXNlcyB0aGUgZGUtbWVhbmVkIGRhdGEgZnJvbSB0aGUgY2VudGVyZWQgZGF0YSBtYXRyaXggJFgkCgpcYmVnaW57ZXF1YXRpb259Clg9XGJlZ2lue2JtYXRyaXh9CiBcdmVydCAgICAmICZcdmVydCBcXCAKIHhfeygxKX0gICZcZG90cyAmeF97KHApfSBcXCAKICBcdmVydCAmICAmIFx2ZXJ0IApcZW5ke2JtYXRyaXh9ClxxdWFkIFx0ZXh0cm17d2l0aH0gClxxdWFkIHhfeyhpKX09XGJlZ2lue2JtYXRyaXh9CnhfaV57KDEpfSBcXApcdmRvdHMgXFwKeF9pXnsobil9ClxlbmR7Ym1hdHJpeH0KXGVuZHtlcXVhdGlvbn0KCi0gUENBIHVzZXMgYSBsaW5lYXIgY29tYmluYXRpb24gb2YgdGhlc2UgY29sdW1ucyB0byBhcnJpdmUgYXQgdGhlIHZlY3RvcnMgb2YgdGhlICoqbmV3IGZlYXR1cmVzKiogJFx0aWxkZXt4fV97KDEpfSxcbGRvdHMsXHRpbGRle3h9X3sobSl9JC4gCgpcWwpcdGlsZGV7eH1feyhpKX0gPSAKdl97aSwxfQpcYmVnaW57Ym1hdHJpeH0KXHZlcnQgIFxcIAogeF97KDEpfSAgXFwgCiBcdmVydCAKXGVuZHtibWF0cml4fQorCnZfe2ksMn0KXGJlZ2lue2JtYXRyaXh9Clx2ZXJ0ICBcXCAKIHhfeygyKX0gIFxcIAogXHZlcnQgClxlbmR7Ym1hdHJpeH0KKyAKfgpcbGRvdHMKfgorCnZfe2kscH0KXGJlZ2lue2JtYXRyaXh9Clx2ZXJ0ICBcXCAKIHhfeyhwKX0gIFxcIAogXHZlcnQgClxlbmR7Ym1hdHJpeH0KXHF1YWQKXHRleHR7Zm9yfQpccXVhZAppPTEsXGxkb3RzLG0sClxdCgotIGVhY2ggbmV3ICRuJCBkaW1lbnNpb25hbCB2ZWN0b3IsICRcdGlsZGV7eH1feyhpKX0kLCBpcyBhICBsaW5lYXIgY29tYmluYXRpb24gb2YgdGhlIG9yaWdpbmFsIGZlYXR1cmVzLgoKCi0gJFx0aWxkZXt4fV97KGkpfSA9IFggdl9pJCB3aGVyZSAkdl9pID0gKHZfe2ksMX0sXGxkb3RzLHZfe2kscH0pJCBpcyBjYWxsZWQgdGhlICoqbG9hZGluZyB2ZWN0b3IqKiBmb3IgJGkkIAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6cGNhLW1hdH0KXHVuZGVyYnJhY2V7XGJlZ2lue2JtYXRyaXh9CiBcdmVydCAmICAgICZcdmVydCBcXCAKIFx0aWxkZXt4fV97KDEpfSAmIFxkb3RzIFxoc3BhY2V7LTAuM2NtfSZcdGlsZGV7eH1feyhtKX0gXFwgCiBcdmVydCAmICAmIFx2ZXJ0IApcZW5ke2JtYXRyaXh9fV97XHVuZGVyc2V0e1x0ZXh0cm17UmVkdWNlZCBkYXRhfX17XHdpZGV0aWxkZXtYfV97blx0aW1lcyBtfX19Cj0KXHVuZGVyYnJhY2V7ClxiZWdpbntibWF0cml4fQogXHZlcnQgJiAgICAmICZcdmVydCBcXCAKIHhfeygxKX0gICAmIFxkb3RzICZcZG90cyAmeF97KHApfSBcXCAKIFx2ZXJ0ICYgICAmJiBcdmVydCAKXGVuZHtibWF0cml4fQp9X3tcdW5kZXJzZXR7XHRleHR7T3JpZ2luYWwgZGUtbWVhbmVkIGRhdGF9fXtYX3tuXHRpbWVzIHB9fX1cdGltZXMgXHVuZGVyYnJhY2V7IFxiZWdpbntibWF0cml4fQogXHZlcnQgJiAgICAmXHZlcnQgXFwgCiBcdmVydCAmICAgICZcdmVydCBcXCAKIHZfMSAmIFxkb3RzICBcaHNwYWNley0wLjNjbX0mdl9tIFxcIAogIFx2ZXJ0ICYgICAgJlx2ZXJ0IFxcIAogXHZlcnQgICYgICYgXHZlcnQgClxlbmR7Ym1hdHJpeH19X3tcdW5kZXJzZXR7XHRleHRybXtNYXRyaXggb2YgbG9hZGluZyB2ZWN0b3JzfX17XHdpZGV0aWxkZXtWfV97cFx0aW1lcyBtfX19LgpcZW5ke2VxdWF0aW9ufQoKPC9kaXY+CgojIyBQQ0Egb24gV2lzY29uc2luIGJyZWFzdCBjYW5jZXIgZGF0YQoKLSBXaXNjb25zaW4gYnJlYXN0IGNhbmNlciBkYXRhOiAgJHA9MzAkIGFuZCAkbj01NjkkLiAKCi0gQWltIHRvICB2aXN1YWxpemUgdGhpcyBkYXRhIHVzaW5nIFBDQSB3ZSBzZXQgJG09MiQgCgpgYGB7cn0KbG9hZCgiQnJlYXN0X2NhbmNlci5SRGF0YSIpCmhlYWQoQnJlYXN0X2NhbmNlcl9kYXRhWyxjKDE6NildKQpkYXRhIDwtIEJyZWFzdF9jYW5jZXJfZGF0YQpkaW0oZGF0YSkKYGBgCgoKYGBge3IsZmlnLndpZHRoPTN9CmxpYnJhcnkoRmFjdG9NaW5lUikKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGRwbHlyKQoKcGNhIDwtIFBDQShkYXRhWywtYygxLDIpXSxuY3A9MixncmFwaD1GQUxTRSkKZGF0IDwtIGRhdGEuZnJhbWUoZGF0YSxwYzE9cGNhJGluZCRjb29yZFssMV0scGMyPXBjYSRpbmQkY29vcmRbLDJdLGRpYWdub3Npcz1hcy5mYWN0b3IoZGF0YVssMl0pKQoKI2RhdCA8LSBkYXQgJT4lIGZpbHRlcihwYzE8NyAmIHBjMjwxMCkgCgpwMSA8LSBnZ3Bsb3QoZGF0YSA9IGRhdCwgYWVzKHggPSBwYzEsIHkgPSBwYzIpKSsKICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSAwLCBsdHkgPSAyKSArCiAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gMCwgbHR5ID0gMikgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjgsc2l6ZT0yLjUpICsgdGhlbWVfYncoKQogCnAxICsgdGhlbWUoYXhpcy50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAyMCkpKyB0aGVtZShheGlzLnRpdGxlID0gZWxlbWVudF90ZXh0KHNpemUgPSAyMCkpICAgCmBgYAoKCi0gVmFyaWFuY2UgZXhwbGFpbmVkIGJ5IHRoZSBmaXJzdCB0d28gY29tcG9uZW50cwoKYGBge3J9CnBjYSRlaWdbMToyLF0KYGBgCgotIENvbG9yIHRoZSBwb2ludHMgYmFzZWQgb24gdGhlIGxhYmVscyBiZW5pZ24gdnMuIG1hbGlnbmFudCwgYSB1c2VmdWwgcGF0dGVybiBlbWVyZ2VzID8KCmBgYHtyLGZpZy53aWR0aD01fQpwMiA8LSBnZ3Bsb3QoZGF0YSA9IGRhdCwgYWVzKHggPSBwYzEsIHkgPSBwYzIsIGNvbG9yID0gZGlhZ25vc2lzKSkrCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0ID0gMCwgbHR5ID0gMikgKwogIGdlb21fdmxpbmUoeGludGVyY2VwdCA9IDAsIGx0eSA9IDIpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC44LHNpemU9Mi41KSArIHRoZW1lX2J3KCkrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPWMoMC4xNSwwLjg1KSxsZWdlbmQudGl0bGU9ZWxlbWVudF9ibGFuaygpKQpwMyA8LSBwMiArICBzY2FsZV9jb2xvcl9kaXNjcmV0ZSggbGFiZWxzID0gYygiYmVuaWduIiwgIm1hbGlnbmFudCIpKQoKcDMgKyB0aGVtZShsZWdlbmQudGV4dD1lbGVtZW50X3RleHQoc2l6ZT0yMCksYXhpcy50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAyMCkpKyB0aGVtZShheGlzLnRpdGxlID0gZWxlbWVudF90ZXh0KHNpemUgPSAyMCkpCmBgYAoKIyMgRGVyaXZhdGlvbiBvZiBQQ0EKCjxkaXYgY2xhc3MgPSAib3JhbmdlIj4KCi0gVGhlIFBDQSBmcmFtZXdvcmsgdHJpZXMgYHIgY29sb3JpemUoInRvIHByb2plY3QgdGhlIGRhdGEgIiwicmVkIilgIGluIHRoZSBkaXJlY3Rpb25zIHdpdGggbWF4aW11bSB2YXJpYW5jZS4gIAoKLSBTaW5jZSAkXHRpbGRle3h9X3soaSl9PVh2X2kkIHdlIGNhbiBmb3JtdWxhdGUgdGhpcyBgciBjb2xvcml6ZSgiYnkgbWF4aW1pemluZyB0aGUgc2FtcGxlIHZhcmlhbmNlIiwicmVkIilgIG9mIHRoZSBjb21wb25lbnRzIG9mICRcdGlsZGV7eH1feyhpKX0kLgoKLSAkXHRpbGRle3h9X3soaSl9JCBpcyBhICQwJCBtZWFuIHZlY3RvciwgaXRzIHNhbXBsZSB2YXJpYW5jZSAgaXMgICRcdGlsZGV7eH1feyhpKX1eXHRvcCBcdGlsZGV7eH1feyhpKX0vbiQuCgotIFdlIGhhdmUsClxbClx0ZXh0e1NhbXBsZSB2YXJpYW5jZSBvZiBjb21wb25lbnR9fmkgPSBcZnJhY3sxfXtufSB2X2leXHRvcCBYXlx0b3AgWCB2X2kgID0gdl9pXlx0b3AgUyB2X2ksClxdCndoZXJlICRTJCBpcyB0aGUgc2FtcGxlIGNvdmFyaWFuY2Ugb2YgdGhlIGRhdGEuCgotIEl0IHR1cm5zIG91dCB0aGUgYSB2ZXJ5IHVzZWZ1bCB3YXkgdG8gcmVwcmVzZW50IHRoZSBsb2FkaW5nIHZlY3RvcnMgJHZfMSxcbGRvdHMsdl9tJCBpcyBieSBgciBjb2xvcml6ZSgibm9ybWVkIGVpZ2VudmVjdG9ycyIsInJlZCIpYCBhc3NvY2lhdGVkIHdpdGggZWlnZW52YWx1ZXMgb2YgdGhlIHNhbXBsZSBjb3ZhcmlhbmNlIG1hdHJpeCAkUyQgCgotICRTJCBpcyBzeW1tZXRyaWMgYW5kICoqcG9zaXRpdmUgc2VtaS1kZWZpbml0ZSoqLCB0aGUgZWlnZW52YWx1ZXMgb2YgJFMkIGFyZSByZWFsIGFuZCBub24tbmVnYXRpdmUsIGEgZmFjdCB3aGljaCBhbGxvd3MgdXMgdG8gb3JkZXIgdGhlbSB2aWEgJFxsYW1iZGFfMSBcZ2UgXGxhbWJkYV8yIFxnZSBcbGRvdHMgXGdlIFxsYW1iZGFfcCBcZ2UgMCQuIAoKLSBXZSB0aGVuIHBpY2sgdGhlIGxvYWRpbmcgdmVjdG9yICR2X2kkIHRvIGJlIGEgKipub3JtZWQgZWlnZW52ZWN0b3IqKiBhc3NvY2lhdGVkIHdpdGggJFxsYW1iZGFfaSQsIG5hbWVseSwKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmVpZy1wY2F9ClMgdl9pID0gXGxhbWJkYV9pIHZfaSwKXGVuZHtlcXVhdGlvbn0KCi0gVGhlIGZpcnN0IGxvYWRpbmcgdmVjdG9yIGlzIGFzc29jaWF0ZWQgd2l0aCB0aGUgYHIgY29sb3JpemUoImhpZ2hlc3QgZWlnZW52YWx1ZSIsInJlZCIpYDsgdGhlIHNlY29uZCBpcyBhc3NvY2lhdGVkIHdpdGggdGhlIHNlY29uZCBoaWdoZXN0IGVpZ2VudmFsdWU7IGFuZCBzbyBmb3VydGguIFRoZSBzeW1tZXRyeSBvZiAkUyQgYWxzbyBtZWFucyB0aGF0IGl0cyBlaWdlbnZlY3RvcnMgYXJlIG9ydGhvZ29uYWwgYW5kIGhlbmNlICRcd2lkZXRpbGRle1Z9JCBpcyBgciBjb2xvcml6ZSgiYSBtYXRyaXggd2l0aCBvcnRob25vcm1hbCBjb2x1bW5zIiwicmVkIilgLiAKCjwvZGl2PgoKIyMgUENBIFRocm91Z2ggU1ZECgo8ZGl2IGNsYXNzID0gImJsdWUiPgoKLSBBbnkgJG4gXHRpbWVzIHAkIGRpbWVuc2lvbmFsIG1hdHJpeCAkWCQgb2YgcmFuayAkciQgY2FuIGJlIHJlcHJlc2VudGVkIGFzIAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6cmVkdWNlZC1zdmR9Clg9VSBcRGVsdGEgVl5cdG9wPVxzdW1fe2k9MX1ee3J9IFxkZWx0YV97aX0gXCwgdV97aX0gXCwgdl97aX1eXHRvcCwKXHF1YWQKXHRleHR7d2l0aH0KXHF1YWQKXERlbHRhPVx0ZXh0cm17ZGlhZ30oXGRlbHRhXzEsXGxkb3RzLFxkZWx0YV9yKSwKXHF1YWQKXHRleHR7YW5kfQpccXVhZApcZGVsdGFfaSA+IDAuClxlbmR7ZXF1YXRpb259CgotICAkbiBcdGltZXMgciQgbWF0cml4ICRVJCBhbmQgdGhlICRwIFx0aW1lcyByJCBtYXRyaXggJFYkIGFyZSBib3RoIHdpdGggb3J0aG9ub3JtYWwgY29sdW1ucyBkZW5vdGVkICR1X2kkIGFuZCAkdl9pJCByZXNwZWN0aXZlbHkgIGZvciAkaT0xLFxsZG90cyxyJC4gCgotIENvbHVtbnMgYXJlIGNhbGxlZCB0aGUgbGVmdCBhbmQgcmlnaHQgKipzaW5ndWxhciB2ZWN0b3JzKiogcmVzcGVjdGl2ZWx5LiAKCi0gJFxkZWx0YV9pJCBpbiB0aGUgJHIgXHRpbWVzIHIkIGRpYWdvbmFsIG1hdHJpeCAkXERlbHRhJCBhcmUgY2FsbGVkICoqc2luZ3VsYXIgdmFsdWVzKiogYW5kIGFyZSBvcmRlcmVkIGFzICRcZGVsdGFfMSBcZ2VxIFxkZWx0YV8yIFxnZXEgXGNkb3RzIFxnZXEgXGRlbHRhX3I+MCQuIAoKIAotIFNWRCByZXByZXNlbnRhdGlvbiBvZiB0aGUgc2FtcGxlIGNvdmFyaWFuY2U6IApcWwpTID0gXGZyYWN7MX17bn0gXHVuZGVyYnJhY2V7VlxEZWx0YV5cdG9wIFVeXHRvcH1fe1hee1x0b3B9fVx1bmRlcmJyYWNle1VcRGVsdGEgVl5cdG9wfV97WH0gPSBcZnJhY3sxfXtufSBWIFxEZWx0YV4yIFZeXHRvcCwKXHF1YWQKXHRleHR7d2l0aH0KXHF1YWQKXERlbHRhXjI9XHRleHRybXtkaWFnfShcZGVsdGFfMV4yLFxsZG90cyxcZGVsdGFfcl4yKS4KXF0KCkhlcmUgdGhlIGZhY3QgdGhhdCAkVSQgaGFzIG9ydGhvbm9ybWFsIGNvbHVtbnMgaW1wbGllcyAkVV5cdG9wIFUkIGlzIHRoZSAkclx0aW1lcyByJCBpZGVudGl0eSBtYXRyaXggYW5kIGhlbmNlIGl0IGNhbmNlbHMgb3V0OiAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOlMtc3ZkfQpTID0gXHN1bV97aT0xfV5yIFxmcmFje1xkZWx0YV9pXjJ9e259IFwsIHZfaSBcLCB2X2leXHRvcC4KXGVuZHtlcXVhdGlvbn0KCjwvZGl2PgoKPGRpdiBjbGFzcyA9ICJvcmFuZ2UiPgotIENvbXBhcmUgdG8gdGhlIGVpZ2VudmVjdG9yIGJhc2VkIHJlcHJlc2VudGF0aW9uIG9mIFBDQToKCi0gVXNpbmcgdGhlIF9TcGVjdHJhbCBkZWNvbXBvc2l0aW9uIG9mICRTJF8KXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6Uy1zcGVjdHJhbH0KUyA9IFx3aWRldGlsZGV7Vn1eXHRvcCBcTGFtYmRhIFx3aWRldGlsZGV7Vn0gPSBcc3VtX3tpPTF9XnIgXGxhbWJkYV9pIFwsdl9pIFwsIHZfaV5cdG9wLgpcZW5ke2VxdWF0aW9ufQoKLSBUaHVzLCAgJFxsYW1iZGFfaT1cZGVsdGFeMl9pL24kIGFuZCB0aGUgbG9hZGluZyB2ZWN0b3JzIGluIHNwZWN0cmFsIGRlY29tcG9zaXRpb24gIGFyZSB0aGUgcmlnaHQgc2luZ3VsYXIgdmVjdG9ycyBpbiBTVkQ6ICAkXHdpZGV0aWxkZXtWfSA9IFYkLgoKLSBGdXJ0aGVyLCB0byBvYnRhaW4gdGhlIGRhdGEgbWF0cml4IG9mIHByaW5jaXBhbCBjb21wb25lbnRzLCAkXHdpZGV0aWxkZXtYfSQgd2Ugc2V0ICRcd2lkZXRpbGRle1h9ID0gWCBWJC4gVXNpbmcgdGhlIFNWRCwgUENBIGNhbiBiZSByZXByZXNlbnRlZDoKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOnBjYS1zdmQtcmVsYXRpb25zaGlwfQpcd2lkZXRpbGRle1h9ID0gXHVuZGVyYnJhY2V7flwsIFUgXERlbHRhIFZeXHRvcH1fe1h9IFYgPSBVIFxEZWx0YSA9ClxiZWdpbntibWF0cml4fQogXHZlcnQgJiBcdmVydCAmICAgICZcdmVydCBcXCAKIFxkZWx0YV8xIHVfMSAmIFxkZWx0YV8yIHVfMiBcaHNwYWNley0wLjNjbX0gJiBcZG90cyAgXGhzcGFjZXstMC4zY219JiBcZGVsdGFfciB1X3IgXFwgCiBcdmVydCAmIFx2ZXJ0ICYgICYgXHZlcnQgClxlbmR7Ym1hdHJpeH0uClxlbmR7ZXF1YXRpb259CgotIEVhY2ggY29sdW1uIG9mIHRoZSByZWR1Y2VkIGRhdGEgbWF0cml4ICRcd2lkZXRpbGRle1h9JCBpcyBhIGxlZnQgc2luZ3VsYXIgdmVjdG9yICR1X2kkIHN0cmV0Y2hlZCBieSB0aGUgc2luZ3VsYXIgdmFsdWUgJFxkZWx0YV9pJC4gCjwvZGl2PgoKIyMgU1ZEIGZvciBDb21wcmVzc2lvbgoKCi0gYHIgY29sb3JpemUoIlRoZSBzaW5ndWxhciB2YWx1ZSBkZWNvbXBvc2l0aW9uIiwicmVkIilgIGNhbiBhbHNvIGJlIHZpZXdlZCBhcyBhIG1lYW5zIGZvciBjb21wcmVzc2luZyBhbnkgbWF0cml4ICRYJC4KCi0gQSByYW5rICRtPHIkIGFwcHJveGltYXRpb24gb2YgJFgkIGlzLAoKXGJlZ2lue2VxdWF0aW9ufQpcbGFiZWx7ZXE6c3ZkLWFwcHJveH0KXHdpZGVoYXR7WH0gPSBcc3VtX3tpPTF9XnttfSBcZGVsdGFfe2l9IFwsIHVfe2l9IFwsIHZfe2l9Xlx0b3AgXGFwcHJveCBYLApccXF1YWQKXHRleHR7d2hlcmV9ClxxcXVhZApYLSBcd2lkZWhhdHtYfSA9ICBcc3VtX3tpPXttKzF9fV57cn0gXGRlbHRhX3tpfSBcLCB1X3tpfSBcLCB2X3tpfV5cdG9wLgpcZW5ke2VxdWF0aW9ufQoKCi0gVGhlIHJhbmsgb2YgJFx3aWRlaGF0e1h9JCBpcyAkbSQgYW5kIHNpbmNlIG9uZSBvZnRlbiB1c2VzICRtJCBzaWduaWZpY2FudGx5IHNtYWxsZXIgdGhhbiAkciQsIHRoaXMgaXMgY2FsbGVkIGEgYHIgY29sb3JpemUoImxvdyByYW5rIGFwcHJveGltYXRpb24iLCJyZWQiKWAuIAoKCi0gRm9yIHNtYWxsIGVub3VnaCAkXGRlbHRhX3ttKzF9JCBgciBjb2xvcml6ZSgidGhlIGFwcHJveGltYXRpb24gZXJyb3IgaXMgbmVnbGlnaWJsZSIsInJlZCIpYCBzaW5jZSB0aGUgc3VtbWF0aW9uIG9mIHJhbmsgb25lIG1hdHJpY2VzICRcZGVsdGFfe2l9IFwsIHVfe2l9IFwsIHZfe2l9Xlx0b3AkIGZvciAkaT1tKzEsXGxkb3RzLHIkIGlzIHNtYWxsLgoKLSBUaGUgbnVtYmVyIG9mIHZhbHVlcyB1c2VkIGluIHRoaXMgcmVwcmVzZW50YXRpb24gb2YgJFx3aWRlaGF0e1h9JCBpcyAkbVx0aW1lcyAoMSsgbiArIHApJCBhbmQgZm9yIHNtYWxsICRtJCB0aGlzIG51bWJlciBpcyBgciBjb2xvcml6ZSgiZ2VuZXJhbGx5IG11Y2ggc21hbGxlciIsImJsdWUiKWAgdGhhbiAkbiBcdGltZXMgcCQgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB2YWx1ZXMgaW4gJFgkLiAKCi0gSGVuY2UgdGhpcyBtYXkgdmlld2VkIGFzIGEgKipjb21wcmVzc2lvbiBtZXRob2QqKi4KCiMjIFNWRCBpbiBhY3Rpb24gZm9yIGNvbXByZXNzaW9uCgotIFdlIHNlZWsgdG8gaGF2ZSB0aGUgYmVzdCByYW5rICRtJCBhcHByb3hpbWF0aW9uIGluIHRlcm1zIG9mIG1pbmltaXphdGlvbiBvZiAkXHxYLVx3aWRlaGF0e1h9XHxfRiQuIAoKLSBGcm9iZW5pb3VzIG5vcm0gbm90ZWQgJFx8IEEgXHxfRiQ6IHNxdWFyZSByb290IG9mIHRoZSBzdW0gb2YgdGhlIHNxdWFyZWQgZWxlbWVudHMgb2YgdGhlIG1hdHJpeCAkQSQKCgotIExvdyByYW5rIGFwcHJveGltYXRpb25zIGVzdGFibGlzaGVkIGJ5ICoqRWNrYXJ04oCTWW91bmctTWlyc2t5IHRoZW9yZW0qKi4gCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTplay15bmd9Clx1bmRlcnNldHtcd2lkZWhhdHtYfVx0ZXh0eyBvZiByYW5rIH1tfXtcbWlufVxsZWZ0XHxYIC0gXHdpZGVoYXR7WH1ccmlnaHRcfF4yX0Y9ICBcbGVmdFx8IFggLSBcc3VtX3tpPTF9XiBtXGRlbHRhX2kgXCwgdV9pIHZfaV57XHRvcH1ccmlnaHRcfF4yX0YgID0gIFxzdW1fe2k9bSsxfV57cn1cZGVsdGFfaV4yLgpcZW5ke2VxdWF0aW9ufQoKLSBjb25zaWRlciBhIHNpbXBsZSB2aXN1YWwgZXhhbXBsZSB3aXRoIGEgJDM1MyBcdGltZXMgNDY5JCBtb25vY2hyb21lIChncmF5c2NhbGUpIGltYWdlIGFwcGVhcmluZyAgdGhpcyBpcyAkWCQuCgohW10oU1ZEX2NvbXByZXNzLnBuZykKCgotIFRoZSBvcmlnaW5hbCBpbWFnZSB1c2VzICQzNTNcdGltZXMgNDY5PTE2NSw1NTckIHZhbHVlcyB3aGlsZSB0aGUgJG09NTAkIGFwcHJveGltYXRpb24gb25seSB1c2VzICQ1MCBcdGltZXMgKDErMzUzKzQ2OSkgPSA0MSwxNTAkIHZhbHVlcy4gVGhhdCBpcyB0aGUgYXBwcm94aW1hdGlvbiB5aWVsZHMgJFx3aWRlaGF0e1h9JCB3aGljaCBpcyBjb21wcmVzc2VkIHRvIGFib3V0ICQyNVwlJCBvZiB0aGUgc2l6ZSBvZiAkWCQgYW5kIGxvb2tzIHZlcnkgc2ltaWxhci4KCiMjIFlvdXIgVHVybgoKLSBBZGFwdCB0aGUgY29kZSB1c2luZyB5b3VyIG93biBpbWFnZQoKYGBge3IsZmlnLndpZHRoPTgsZmlnLmhlaWdodD0xMCxldmFsPUZBTFNFfQppZiAoISJqcGVnIiAlaW4lIGluc3RhbGxlZC5wYWNrYWdlcygpKSBpbnN0YWxsLnBhY2thZ2VzKCJqcGVnIikKIyBSZWFkIGltYWdlIGZpbGUgaW50byBhbiBhcnJheSB3aXRoIHRocmVlIGNoYW5uZWxzIChSZWQtR3JlZW4tQmx1ZSwgUkdCKQpteUltYWdlIDwtIGpwZWc6OnJlYWRKUEVHKCJDT0RFX1dPUktTSE9QL3Bvb2xfZ3JheXNhY2xlLmpwZyIpCgpyIDwtIG15SW1hZ2VbLCAsIDFdIAojIFBlcmZvcm1zIGZ1bGwgU1ZEIApteUltYWdlLnIuc3ZkIDwtIHN2ZChyKSMgOyBsbXlJbWFnZS5nLnN2ZCA8LSBzdmQoZykgOyBteUltYWdlLmIuc3ZkIDwtIHN2ZChiKQpyZ2Iuc3ZkcyA8LSBsaXN0KG15SW1hZ2Uuci5zdmQpIwoKCgpwbG90LmltYWdlIDwtIGZ1bmN0aW9uKHBpYywgbWFpbiA9ICIiKSB7CiAgaCA8LSBkaW0ocGljKVsxXSA7IHcgPC0gZGltKHBpYylbMl0KICBwbG90KHggPSBjKDAsIGgpLCB5ID0gYygwLCB3KSwgdHlwZSA9ICJuIiwgeGxhYiA9ICIiLCB5bGFiID0gIiIsIG1haW4gPSBtYWluKQogIHJhc3RlckltYWdlKHBpYywgMCwgMCwgaCwgdykKfQoKCmNvbXByZXNzLmltYWdlIDwtIGZ1bmN0aW9uKHJnYi5zdmRzLCBuYi5jb21wKSB7CiAgIyBuYi5jb21wIChudW1iZXIgb2YgY29tcG9uZW50cykgc2hvdWxkIGJlIGxlc3MgdGhhbiBtaW4oZGltKGltZ1ssLDFdKSksIAogICMgaS5lLiwgMTcwIGhlcmUKICBzdmQubG93ZXIuZGltIDwtIGxhcHBseShyZ2Iuc3ZkcywgZnVuY3Rpb24oaSkgbGlzdChkID0gaSRkWzE6bmIuY29tcF0sIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHUgPSBpJHVbLCAxOm5iLmNvbXBdLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2ID0gaSR2WywgMTpuYi5jb21wXSkpCiAgaW1nIDwtIHNhcHBseShzdmQubG93ZXIuZGltLCBmdW5jdGlvbihpKSB7CiAgICBpbWcuY29tcHJlc3NlZCA8LSBpJHUgJSolIGRpYWcoaSRkKSAlKiUgdChpJHYpCiAgfSwgc2ltcGxpZnkgPSAnYXJyYXknKQogIGltZ1tpbWcgPCAwXSA8LSAwCiAgaW1nW2ltZyA+IDFdIDwtIDEKICByZXR1cm4obGlzdChpbWcgPSBpbWcsIHN2ZC5yZWR1Y2VkID0gc3ZkLmxvd2VyLmRpbSkpCn0KCgoKcGFyKG1mcm93ID0gYygyLCAyKSkKcGxvdC5pbWFnZShyLCAiT3JpZ2luYWwgaW1hZ2UiKQoKcCA8LSAxMCA7IHBsb3QuaW1hZ2UoY29tcHJlc3MuaW1hZ2UocmdiLnN2ZHMsIHApJGltZ1ssLDFdLCAKICAgICAgICAgICAgICAgICAgICAgcGFzdGUoIlNWRCB3aXRoIiwgcCwgImNvbXBvbmVudHMiKSkKCnAgPC0gMzAgOyBwbG90LmltYWdlKGNvbXByZXNzLmltYWdlKHJnYi5zdmRzLCBwKSRpbWdbLCwxXSwgCiAgICAgICAgICAgICAgICAgICAgIHBhc3RlKCJTVkQgd2l0aCIsIHAsICJjb21wb25lbnRzIikpCgoKcCA8LSA1MCA7IHBsb3QuaW1hZ2UoY29tcHJlc3MuaW1hZ2UocmdiLnN2ZHMsIHApJGltZ1ssLDFdLCAKICAgICAgICAgICAgICAgICAgICAgcGFzdGUoIlNWRCB3aXRoIiwgcCwgImNvbXBvbmVudHMiKSkKCmBgYAoKCiMgQSB0YXN0ZSBvZiBTaGFsbG93IEF1dG9lbmNvZGVycwoKCi0gQSBzY2hlbWF0aWMgb2YgYW4gYXV0b2VuY29kZXIgd2l0aCBhIHNpbmdsZSAqKmhpZGRlbiBsYXllcioqLiAKCiFbXShhdXRvZW5jb2Rlci5wbmcpCgoKPGRpdiBjbGFzcyA9ICJibHVlIj4KLSBUaGUgaW5wdXQgJHggXGluIFxSZV5wJCBpcyB0cmFuc2Zvcm1lZCBpbnRvIGEgKipib3R0bGVuZWNrKiosIGFsc28gY2FsbGVkIHRoZSAqKmNvZGUqKiB3aGljaCBpcyBzb21lICRcdGlsZGV7eH0gXGluIFxSZV5tJCBhbmQgaXMgdGhlIGhpZGRlbiBsYXllciBvZiB0aGUgbW9kZWwuIAoKLSBUaGVuIHRoZSAqKmJvdHRsZW5lY2sqKiBpcyBmdXJ0aGVyIHRyYW5zZm9ybWVkIGludG8gdGhlIG91dHB1dCAkXGhhdHt4fSBcaW4gXFJlXnAkLiAKCi0gVGhlIHBhcnQgb2YgdGhlIGF1dG9lbmNvZGVyIHRoYXQgdHJhbnNmb3JtcyB0aGUgaW5wdXQgaW50byB0aGUgYm90dGxlbmVjayBpcyBjYWxsZWQgdGhlIGByIGNvbG9yaXplKCJlbmNvZGVyIiwicmVkIilgIGFuZCB0aGUgcGFydCBvZiB0aGUgYXV0b2VuY29kZXIgdGhhdCB0cmFuc2Zvcm1zIHRoZSBib3R0bGVuZWNrIHRvIHRoZSBvdXRwdXQgaXMgY2FsbGVkIHRoZSBgciBjb2xvcml6ZSgiZGVjb2RlciIsInJlZCIpYC4gQm90aCB0aGUgZW5jb2RlciBhbmQgdGhlIGRlY29kZXIgaGF2ZSBwYXJhbWV0ZXJzIHRoYXQgYXJlIHRvIGJlIGByIGNvbG9yaXplKCJsZWFybmVkIiwiYmx1ZSIpYC4KCi0gSW50ZXJlc3RpbmdseSBmb3IgaW5wdXQgJHgkLCBvbmNlIHBhcmFtZXRlcnMgYXJlIHRyYWluZWQsIHdlIGdlbmVyYWxseSBleHBlY3QgdGhlIGF1dG9lbmNvZGVyIHRvIGdlbmVyYXRlIG91dHB1dCAkXGhhdHt4fSQgdGhhdCBpcyBhcyBgciBjb2xvcml6ZSgic2ltaWxhciIsImJsdWUiKWAgdG8gdGhlIGlucHV0ICR4JCBhcyBwb3NzaWJsZS4gCgotIENvbnNpZGVyIHRoZSBhY3Rpdml0eSBvZiBkYXRhIHJlZHVjdGlvbiB3aGVyZSB0aGUgIGRpbWVuc2lvbiBvZiB0aGUgYm90dGxlbmVjayAkbSQgaXMgYHIgY29sb3JpemUoInNpZ25pZmljYW50bHkgc21hbGxlciIsImJsdWUiKWAgdGhhbiB0aGUgaW5wdXQgYW5kIG91dHB1dCBkaW1lbnNpb24gJHAkIAoKPC9kaXY+CgoKLSBGb3IgZXhhbXBsZSwgcmV0dXJuIHRvIHRoZSBjYXNlIG9mIE1OSVNUIGRpZ2l0cyB3aGVyZSAkcD03ODQkLiBGb3Igb3VyIGV4YW1wbGUgaGVyZSwgYXNzdW1lIHdlIGhhdmUgYW4gYXV0byBlbmNvZGVyIHdpdGggJG09MzAkLiAKCiFbXShyZWNvbnRyc3VjdGlvbl9BRS5wbmcpCgotIEEgdHJhaW5lZCBhdXRvZW5jb2RlciB5aWVsZHMgJHggXGFwcHJveCBcaGF0e3h9JCB0aGVuIGl0IG1lYW5zIHRoYXQgd2UgaGF2ZSBhbiBpbW1lZGlhdGUgZGF0YSByZWR1Y3Rpb24gbWV0aG9kLiAKCi0gYHIgY29sb3JpemUoIldpdGggdGhlIHRyYWluZWQgZW5jb2RlciIsImJsdWUiKWAgd2UgYXJlIGFibGUgdG8gY29udmVydCBkaWdpdCBpbWFnZXMsIGVhY2ggb2Ygc2l6ZSAkMjggXHRpbWVzIDI4ID0gNzg0JCwgaW50byBtdWNoIHNtYWxsZXIgdmVjdG9ycywgZWFjaCBvZiBzaXplICQzMCQuIAoKLSBXaXRoIHRoZSB0cmFpbmVkIGRlY29kZXIgd2UgYXJlIGFibGUgdG8gYHIgY29sb3JpemUoImNvbnZlcnQgYmFjayBhbmQgZ2V0IGFuIGFwcHJveGltYXRpb24gb2YgdGhlIG9yaWdpbmFsIGltYWdlIiwiYmx1ZSIpYC4gVGhpcyBjaG9pY2Ugb2YgJG0kIGltcGxpZXMgYSByYXRoZXIgcmVtYXJrYWJsZSBgciBjb2xvcml6ZSgiY29tcHJlc3Npb24iLCJyZWQiKWAgZmFjdG9yIG9mIGFib3V0ICQyNiQuCgojIyBBdXRvZW5jb2RlciBsb3NzIAoKPGRpdiBjbGFzcyA9ICJibHVlIj4KLSBUaGUgbW9zdCBzdHJhaWdodGZvcndhcmQgY2hvaWNlIGZvciB0aGUgZGlzdGFuY2UgcGVuYWx0eSBpbiAgJENfaShcdGhldGEpJCBpcyB0aGUgc3F1YXJlIG9mIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2U6CgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcTphdXRvZW5jb2Rlci1sb3NzfQpDX2koXHRoZXRhKSA9IFx8IHheeyhpKX0gLSBmX1x0aGV0YSh4XnsoaSl9KSBcfF4yClxxdWFkClx0ZXh0e2FuZCB0aHVzfQpccXVhZApDKFx0aGV0YSBcLCA7IFwsIFxtYXRoY2FsIEQpID0gIFxmcmFjezF9e259IFxzdW1fe2k9MX1ebiAgXHwgeF57KGkpfSAtIGZfXHRoZXRhKHheeyhpKX0pIFx8XjIuClxlbmR7ZXF1YXRpb259CgpXaXRoIHRoaXMgbG9zcyBzdHJ1Y3R1cmUsIGxlYXJuaW5nIHRoZSBwYXJhbWV0ZXJzLCAkXHRoZXRhJCwgb2YgYW4gYXV0b2VuY29kZXIgYmFzZWQgb24gZGF0YSAkXG1hdGhjYWwgRCQgaXMgdGhlIHByb2Nlc3Mgb2YgYHIgY29sb3JpemUoIm1pbmltaXppbmciLCJyZWQiKWAgJEMoXHRoZXRhIFwsIDsgXCwgXG1hdGhjYWwgRCQuIAo8L2Rpdj4KCjxkaXYgY2xhc3MgPSAib3JhbmdlIj4KCi0gRGVjb21wb3NlICRmX1x0aGV0YShcY2RvdCkkIHRvIGJlIGEgY29tcG9zaXRpb24gb2YgdGhlIGVuY29kZXIgZnVuY3Rpb24gZGVub3RlZCB2aWEgJGZee1sxXX1fe1x0aGV0YV57WzFdfX0oXGNkb3QpJCBhbmQgdGhlIGRlY29kZXIgZnVuY3Rpb24gZGVub3RlZCB2aWEgJGZee1syXX1fe1x0aGV0YV57WzJdfX0oXGNkb3QpJDoKClxbClxoYXR7eH0gPSBmX1x0aGV0YSh4KSA9ICBcYmlnKGZee1syXX1fe1x0aGV0YV57WzJdfX0gXGNpcmMgIGZee1sxXX1fe1x0aGV0YV57WzFdfX1cYmlnKSAoeCkgPSBmXntbMl19X3tcdGhldGFee1syXX19XGJpZyggZl57WzFdfV97XHRoZXRhXntbMV19fSh4KSBcYmlnKSwKXF0KCi0gV2UgZGVmaW5lLAoKXGJlZ2lue2VxdWF0aW9ufQogXGxhYmVse2VxOmVuY29kZXItZGVjb2Rlcn0KXGJlZ2lue2FycmF5fXtyY2x9CiBmXntbMV19X3tcdGhldGFee1sxXX19KHUpJj0mU157WzFdfShiXntbMV19ICsgV157WzFdfSB1KSBccXVhZCBcdGV4dHtmb3J9IFxxdWFkIHUgXGluIFxSZV5wICBccXF1YWQgKFx0ZXh0cm17RW5jb2Rlcn0pXFwKZl57WzJdfV97XHRoZXRhXntbMl19fSh1KSY9JlNee1syXX0oYl57WzJdfSArIFdee1syXX0gdSkgXHF1YWQgXHRleHR7Zm9yfSBccXVhZCB1IFxpbiBcUmVebSBccXF1YWQgIChcdGV4dHJte0RlY29kZXJ9KSwKXGVuZHthcnJheX0KXGVuZHtlcXVhdGlvbn0KCjwvZGl2PgoKLSBUaGUgKiplbmNvZGVyIHBhcmFtZXRlcnMqKiAkXHRoZXRhXntbMV19JCBhcmUgY29tcG9zZWQgb2YgdGhlIGJpYXMgJGJee1sxXX1caW4gXFJlXnttfSQgYW5kICB3ZWlnaHQgbWF0cml4ICRXXntbMV19XGluIFxSZV57bSBcdGltZXMgcH0kCgotIFRoZSAqKmRlY29kZXIgcGFyYW1ldGVycyoqICRcdGhldGFee1syXX0kIGFyZSBjb21wb3NlZCBvZiB0aGUgYmlhcyAkYl57WzJdfVxpbiBcUmVee3B9JCBhbmQgIHdlaWdodCBtYXRyaXggJFdee1syXX1caW4gXFJlXntwIFx0aW1lcyBtfSQuIAoKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmNvbXBldGUtMmxheWVyLWF1dG8tdGhldGF9Clx0aGV0YSA9IChiXntbMV19LFdee1sxXX0sYl57WzJdfSxXXntbMl19KS4KXGVuZHtlcXVhdGlvbn0gCgotICBWZWN0b3IgYWN0aXZhdGlvbiBmdW5jdGlvbnMgJFNee1sxXX0oXGNkb3QpJCBhbmQgJFNee1syXX0oXGNkb3QpJDogIHdlIGNvbnN0cnVjdCB0aGVzZSBiYXNlZCBvbiBzY2FsYXIgYWN0aXZhdGlvbiBmdW5jdGlvbnMgJFxzaWdtYV57W1xlbGxdfTogXFJlIFx0byBcUmUkIGZvciAkXGVsbD0xLDIkLgoKLSBTcGVjaWZpY2FsbHksIHdlIHNldCAkU157W1xlbGxdfSh6KSQgdG8gYmUgdGhlIGVsZW1lbnQgd2lzZSBhcHBsaWNhdGlvbiBvZiAkXHNpZ21hXntbXGVsbF19KFxjZG90KSQgb24gZWFjaCBvZiB0aGUgY29vcmRpbmF0ZXMgb2YgJHokCgpcYmVnaW57ZXF1YXRpb259ClxsYWJlbHtlcW46YWN0aXZhdGlvbi1mdW5jdGlvbi12ZWN0b3J9ClNee1tcZWxsXX0oeik9XGxlZnRbClxiZWdpbnttYXRyaXh9ClxzaWdtYV57W1xlbGxdfVxsZWZ0KHpfezF9XHJpZ2h0KSBcXApcdmRvdHNcXAogXHNpZ21hXntbXGVsbF19XGxlZnQoel97cn1ccmlnaHQpCiBcZW5ke21hdHJpeH0KIFxyaWdodF0uClxlbmR7ZXF1YXRpb259CgotIFRoZSBsb3NzIGZ1bmN0aW9uIHJlcHJlc2VudGF0aW9uIGFzLCAKClxiZWdpbntlcXVhdGlvbn0KXGxhYmVse2VxOmNvc3RhdXRvZW5jb2Rlcn0KQyhcdGhldGEgXCwgOyBcLFxtYXRoY2FsIEQpPVxmcmFjezF9e259IFxzdW1fe2k9MX1eblwgXHx4XnsoaSl9LVx1bmRlcmJyYWNle1Nee1syXX0oV157WzJdfVNee1sxXX0oV157WzFdfXheeyhpKX0rYl57WzFdfSkrYl57WzJdfSl9X3tmX3tcdGhldGF9KHheeyhpKX0pfVx8XjIuClxlbmR7ZXF1YXRpb259CgotIFdpdGggdGhpcyBsb3NzIGZ1bmN0aW9uLCBmb3IgZ2l2ZW4gZGF0YSAkXG1hdGhjYWwgRCQsIHRoZSBsZWFybmVkIGF1dG9lbmNvZGVyIHBhcmFtZXRlcnMgJFxoYXR7XHRoZXRhfSQgYXJlIGdpdmVuIGJ5IGEgc29sdXRpb24gdG8gIHRoZSBvcHRpbWl6YXRpb24gcHJvYmxlbSAkXHRleHR7bWlufV9cdGhldGEgQyhcdGhldGEgXCwgOyBcLFxtYXRoY2FsIEQpJC4gCgoKIyMgIFBDQSBpcyBhbiBBdXRvZW5jb2RlcgoKLSBBdXRvZW5jb2RlcnMgYHIgY29sb3JpemUoImdlbmVyYWxpemUgcHJpbmNpcGFsIGNvbXBvbmVudCBhbmFseXNpcyIsInJlZCIpYCAoUENBKQoKLSBQQ0EgaXMgZXNzZW50aWFsbHkgYSBgciBjb2xvcml6ZSgic2hhbGxvdyBhdXRvLWVuY29kZXIgd2l0aCBpZGVudGl0eSBhY3RpdmF0aW9uIGZ1bmN0aW9ucyIsImJsdWUiKWAgJFxzaWdtYV57W1xlbGxdfSh1KSA9IHUkIGZvciAkXGVsbD0xLDIkLCBhbHNvIGtub3duIGFzIGEgKipsaW5lYXIgYXV0b2VuY29kZXIqKi4gCgotIFBDQSB5aWVsZHMgb25lIHBvc3NpYmxlIHNvbHV0aW9uIHRvIHRoZSBsZWFybmluZyBvcHRpbWl6YXRpb24gcHJvYmxlbSBmb3IgbGluZWFyIGF1dG9lbmNvZGVycy4KCgohW10oUENBX2F1dG9lbmNvZGVyLnBuZykKCiMjIEF1dG9lbmNvZGVyIG9uIE1OSVNUCgotIGNvbnNpZGVyIHVzaW5nIGFuIGF1dG9lbmNvZGVyIG9uIE1OSVNUIHdoZXJlICRwPTI4XHRpbWVzMjggPSA3ODQkIGFuZCB3ZSB1c2UgJG09MiQuIAoKLSBXZSBlbmNvZGUgdGhpcyB2aWEgKipQQ0EqKiwgYSBzaGFsbG93IG5vbi1saW5lYXIgYXV0b2VuY29kZXIsIGFuZCBhIGByIGNvbG9yaXplKCJkZWVwIGF1dG9lbmRvZXIiLCJyZWQiKWAgdGhhdCBoYXMgaGlkZGVuIGxheWVycy4gCgotIFRoZSBhdXRvZW5jb2RlcnMgYXJlIHRyYWluZWQgb24gdGhlIHRyYWluaW5nIHNldCBhbmQgdGhlIGNvZGVzIHByZXNlbnRlZCBhcmUgYm90aCBmb3IgdGhlIHRyYWluaW5nIHNldCwgYW5kIGZvciB0aGUgdGVzdGluZyBzZXQgZGF0YS4KCi0gV2UgY29sb3IgdGhlIGNvZGUgcG9pbnRzIGJhc2VkIG9uIHRoZSBsYWJlbHMuIFRoaXMgYWxsb3dzIHVzIHRvIHNlZSBob3cgZGlmZmVyZW50IGxhYmVscyBhcmUgZ2VuZXJhbGx5IGVuY29kZWQgb250byBkaWZmZXJlbnQgcmVnaW9ucyBvZiB0aGUgY29kZSBzcGFjZS4gCgoKIVtdKE1OSVNUX2F1dG9lbmNvZGVyLnBuZykKCgotIE9uZSBhcHBsaWNhdGlvbiBvZiBzdWNoIGByIGNvbG9yaXplKCJkYXRhIHJlZHVjdGlvbiIsInJlZCIpYCBpcyB0byBoZWxwIHNlcGFyYXRlIHRoZSBkYXRhCgotIEl0IGlzIGV2aWRlbnQgdGhhdCBhcyBtb2RlbCBjb21wbGV4aXR5IGluY3JlYXNlcyAgYHIgY29sb3JpemUoImJldHRlciBzZXBhcmF0aW9uIiwicmVkIilgIG9jY3VycyBpbiB0aGUgZGF0YS4gIAoKLSBgciBjb2xvcml6ZSgiSW4gdGVybXMgb2YgcmVjb25zdHJ1Y3Rpb24iLCJibHVlIilgLCBpdCBpcyBhbHNvIGV2aWRlbnQgaW4gdGhpcyBjYXNlIHRoYXQgbW9yZSBjb21wbGV4IG1vZGVscyBleGhpYml0IGJldHRlciByZWNvbnN0cnVjdGlvbiBhYmlsaXR5LgoKIyMgQSBkZW5vaXNpbmcgYXV0b2VuY29kZXIKCi0gVGhpcyBtb2RlbCBsZWFybnMgdG8gYHIgY29sb3JpemUoInJlbW92ZSBub2lzZSIsImJsdWUiKWAgZHVyaW5nIHRoZSByZWNvbnN0cnVjdGlvbiBzdGVwIGZvciBub2lzeSBpbnB1dCBkYXRhLgoKLSBJdCB0YWtlcyBpbiBgciBjb2xvcml6ZSgicGFydGlhbGx5IGNvcnJ1cHRlZCBpbnB1dCIsImJsdWUiKWAgYW5kIGxlYXJucyB0byByZWNvdmVyIHRoZSBvcmlnaW5hbCBkZW5vaXNlZCBpbnB1dC4gCgotIEl0IHJlbGllcyBvbiB0aGUgaHlwb3RoZXNpcyB0aGF0IGhpZ2gtbGV2ZWwgcmVwcmVzZW50YXRpb25zIGFyZSByZWxhdGl2ZWx5IHN0YWJsZSBhbmQgcm9idXN0IHRvIGVudHJ5IGNvcnJ1cHRpb24gYW5kIHRoYXQgdGhlIG1vZGVsIGlzIGByIGNvbG9yaXplKCJhYmxlIHRvIGV4dHJhY3QiLCJibHVlIilgIGNoYXJhY3RlcmlzdGljcyB0aGF0IGFyZSB1c2VmdWwgZm9yIHRoZSByZXByZXNlbnRhdGlvbiBvZiB0aGUgaW5wdXQgZGlzdHJpYnV0aW9uLiAKCgohW10ocmVjb25zdHJ1Y3RpbmdfaW5wdXQucG5nKQoKIyMjIFlvdXIgdHVybgoKLSBUcnkgdGhlIGZvbGxvd2luZyBbZGVub2lzaW5nIGV4YW1wbGVdKGh0dHBzOi8vcnV0YS5zb2Z0d2FyZS9hcnRpY2xlcy9leGFtcGxlcy9hdXRvZW5jb2Rlcl9kZW5vaXNpbmcuaHRtbCkKCgojIyBJbnRlcnBvbGF0aW9uIG9uIHRoZSBsYXRlbnQgc3BhY2UKCgoKLSBUYWtlICR4XnsoaSl9JCBhbmQgJHheeyhqKX0kIGZyb20gJFxtYXRoY2FsIEQgPSBce3heeygxKX0sXGxkb3RzLHheeyhuKX1cfSQgYW5kIGNvbnNpZGVyIHRoZSBjb252ZXggY29tYmluYXRpb24KXFsKeF9cbGFtYmRhXntcdGV4dHtuYWl2ZX19ID0gXGxhbWJkYSB4XnsoaSl9ICsgKDEtXGxhbWJkYSkgeF57KGopfSwKXF0KZm9yIHNvbWUgJFxsYW1iZGEgXGluIFswLDFdJC4gCgoKLSAkeF9cbGFtYmRhXntcdGV4dHtuYWl2ZX19JCBpcyBhIGByIGNvbG9yaXplKCJ3ZWlnaHRlZCBhdmVyYWdlIGJldHdlZW4gdGhlIHR3byBvYnNlcnZhdGlvbnMiLCJibHVlIilgLgoKLSAkXGxhbWJkYSQgIGNhcHR1cmVzIHdoaWNoIG9mIHRoZSBvYnNlcnZhdGlvbnMgaGFzIG1vcmUgd2VpZ2h0LgoKLSBTdWNoIGFyaXRobWV0aWMgb24gdGhlIGFzc29jaWF0ZWQgZmVhdHVyZSB2ZWN0b3JzIGlzIGByIGNvbG9yaXplKCJ0b28gbmFpdmUgYW5kIG9mdGVuIG1lYW5pbmdsZXNzIiwiYmx1ZSIpYC4KCi0gV2hlbiBjb25zaWRlcmluZyB0aGUgbGF0ZW50IHNwYWNlIHJlcHJlc2VudGF0aW9uIG9mIHRoZSBpbWFnZXMgaXQgaXMgb2Z0ZW4gcG9zc2libGUgdG8gY3JlYXRlIGEgbXVjaCBtb3JlIG1lYW5pbmdmdWwgaW50ZXJwb2xhdGlvbiBiZXR3ZWVuIHRoZSBpbWFnZXMuIAoKIVtdKGludGVycG9sLnBuZykKCgotIFRyYWluIGFuIGF1dG9lbmNvZGVyIGFuZCB0aGVuIGVuY29kZSAkeF57KGkpfSQgYW5kICR4Xnsoail9JCB0byBvYnRhaW4gJFx0aWxkZXt4fV57KGkpfSQgYW5kICRcdGlsZGV7eH1eeyhqKX0kLiAKCi0gVGhlbiBgciBjb2xvcml6ZSgiaW50ZXJwb2xhdGUgb24gdGhlIGNvZGVzIiwicmVkIilgLCBhbmQgZmluYWxseSBkZWNvZGUgJFx0aWxkZXt4fV9cbGFtYmRhJCB0byBvYnRhaW4gYW4gaW50ZXJwb2xhdGVkIGltYWdlLgoKXFsKe3h9X1xsYW1iZGFee1x0ZXh0e2VuY29kZXJ9fSA9IGZee1syXX0gXEJpZyhcbGFtYmRhIGZee1sxXX0oe3h9XnsoaSl9KSArICgxLVxsYW1iZGEpIGZee1sxXX0oe3h9Xnsoail9KSBcQmlnKS4KXF0KCi0gb25lIHBvdGVudGlhbCBhcHBsaWNhdGlvbiBvZiBzdWNoIGludGVycG9sYXRpb24gaXMgZm9yIGByIGNvbG9yaXplKCJkZXNpZ24gcHVycG9zZXMiLCJyZWQiKWAsIHNheSBpbiBhcnQgb3IgYXJjaGl0ZWN0dXJlLCB3aGVyZSBvbmUgY2hvb3NlcyB0d28gc2FtcGxlcyBhcyBhIHN0YXJ0aW5nIHBvaW50IGFuZCB0aGVuIHVzZXMgaW50ZXJwb2xhdGlvbiB0byBzZWUgb3RoZXIgc2FtcGxlcyBseWluZyBgYGluIGJldHdlZW4nJy4gCgoKIyMjIFJ1dGEgUiBwYWNrYWdlIGZvciBhdXRvZW5jb2RlcgoKVGhlIGZvbGxvd2luZyBjb2dlIHdpbGwgdGFrZSBzb21lIHRpbWVzIHRvIHJ1biAKCmBgYHtyLGV2YWw9VFJVRSxjYWNoZT1UUlVFLG1lc3NhZ2U9RkFMU0V9CiMgVG8gaW5zdGFsbCB0aGUgUiBwYWNrYWdlIGRvd25sYW9kIHRoZSB0YXIuZ3ogZmlsZSBhdCBodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy9zcmMvY29udHJpYi9BcmNoaXZlL3J1dGEvCmxpYnJhcnkocnV0YSkKbGlicmFyeShyQVJQQUNLKQpsaWJyYXJ5KGdncGxvdDIpCiMjIyMjIyMjIyMjIyMjIwojIyMgRnVuY3Rpb24gcGxvdCAKIyMjIyMjIyMjIyMjIyMjCnBsb3RfZGlnaXQgPC0gZnVuY3Rpb24oZGlnaXQsIC4uLikgewogIGltYWdlKGtlcmFzOjphcnJheV9yZXNoYXBlKGRpZ2l0LCBjKDI4LCAyOCksICJGIilbLCAyODoxXSwgeGF4dCA9ICJuIiwgeWF4dCA9ICJuIiwgY29sPWdyYXkoMToyNTYgLyAyNTYpLCAuLi4pCn0KCnBsb3Rfc2FtcGxlIDwtIGZ1bmN0aW9uKGRpZ2l0c190ZXN0LCBtb2RlbDEsbW9kZWwyLG1vZGVsMywgc2FtcGxlKSB7CiAgc2FtcGxlX3NpemUgPC0gbGVuZ3RoKHNhbXBsZSkKICBsYXlvdXQoCiAgICBtYXRyaXgoYygxOnNhbXBsZV9zaXplLCAoc2FtcGxlX3NpemUgKyAxKTooNCAqIHNhbXBsZV9zaXplKSksIGJ5cm93ID0gRiwgbnJvdyA9IDQpCiAgKQogIAogIAogIGZvciAoaSBpbiBzYW1wbGUpIHsKICAgIHBhcihtYXIgPSBjKDAsMCwwLDApICsgMSkKICAgIHBsb3RfZGlnaXQoZGlnaXRzX3Rlc3RbaSwgXSkKICAgIHBsb3RfZGlnaXQobW9kZWwxW2ksIF0pCiAgICBwbG90X2RpZ2l0KG1vZGVsMltpLCBdKQogICAgcGxvdF9kaWdpdChtb2RlbDNbaSwgXSkKICB9Cn0KCgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIyMjIExvYWQgTU5JU1QgREFUQQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwoKbW5pc3QgPSBrZXJhczo6ZGF0YXNldF9tbmlzdCgpCgojIE5vcm1hbGl6YXRpb24gdG8gdGhlIFswLCAxXSBpbnRlcnZhbAp4X3RyYWluIDwtIGtlcmFzOjphcnJheV9yZXNoYXBlKAogIG1uaXN0JHRyYWluJHgsIGMoZGltKG1uaXN0JHRyYWluJHgpWzFdLCA3ODQpCikKeF90cmFpbiA8LSB4X3RyYWluIC8gMjU1LjAKeF90ZXN0IDwtIGtlcmFzOjphcnJheV9yZXNoYXBlKAogIG1uaXN0JHRlc3QkeCwgYyhkaW0obW5pc3QkdGVzdCR4KVsxXSwgNzg0KQopCnhfdGVzdCA8LSB4X3Rlc3QgLyAyNTUuMAoKaWYoVCl7Cm5ldHdvcmsgPC0gaW5wdXQoKSArIGRlbnNlKDMwLCAidGFuaCIpICsgb3V0cHV0KCJzaWdtb2lkIikKbmV0d29yazEgPC0gaW5wdXQoKSArIGRlbnNlKDUwLCAidGFuaCIpICtkZW5zZSgxMCwgImxpbmVhciIpK2RlbnNlKDUwLCAidGFuaCIpICtvdXRwdXQoInNpZ21vaWQiKQp9CgojIyMgbW9kZWwgc2ltcGxlCm5ldHdvcmsuc2ltcGxlIDwtIGF1dG9lbmNvZGVyKG5ldHdvcmspIywgbG9zcyA9ICJiaW5hcnlfY3Jvc3NlbnRyb3B5IikKbW9kZWwgPSB0cmFpbihuZXR3b3JrLnNpbXBsZSwgeF90cmFpbiwgZXBvY2hzID0gMTApCmRlY29kZWQuc2ltcGxlIDwtIHJlY29uc3RydWN0KG1vZGVsLCB4X3Rlc3QpCgoKIyMjIG1vZGVsIGRlZXAKbXlfYWUyIDwtIGF1dG9lbmNvZGVyKG5ldHdvcmsxKSMsIGxvc3MgPSAiYmluYXJ5X2Nyb3NzZW50cm9weSIpCm1vZGVsMiA9IHRyYWluKG15X2FlMiwgeF90cmFpbiwgZXBvY2hzID0gMTApCmRlY29kZWQyIDwtIHJlY29uc3RydWN0KG1vZGVsMiwgeF90ZXN0KQoKIyMjIyBMaW5lYXIgaW50ZXJwb2xhdGlvbiBiZXR3ZWVuIHR3byBkaWdpdHMKZGlnaXRfQSA9IHhfdHJhaW5bd2hpY2gobW5pc3QkdHJhaW4keT09MylbMV0sXSNNTklTVCBkaWdpdCB3aXRoIDMgKFRoaXMgaXMgdGhlIGZpcnN0IGRpZ2l0IGluIHRoZSB0cmFpbiBzZXQgdGhhdCBoYXMgMykKZGlnaXRfQiA9IHhfdHJhaW5bd2hpY2gobW5pc3QkdHJhaW4keT09MylbMTBdLF0jYW5vdGhlciBNTklTVCBkaWdpdCB3aXRoIDMgKFRoaXMgaXMgdGhlIDEwW3RoXSBkaWdpdCBpbiB0aGUgdHJhaW4gc2V0IHRoYXQgaGFzIDMpCmxhdGVudF9BID0gZW5jb2RlKG1vZGVsMixtYXRyaXgoZGlnaXRfQSxucm93PTEpKQpsYXRlbnRfQiA9IGVuY29kZShtb2RlbDIsbWF0cml4KGRpZ2l0X0IsbnJvdz0xKSkKbGFtYmRhID0gMC41CmxhdGVudF9pbnRlcnBvbGF0aW9uID0gbGFtYmRhKmxhdGVudF9BICsgKDEtbGFtYmRhKSpsYXRlbnRfQgpyb3VnaHRfaW50ZXJwb2xhdGlvbiA9IGxhbWJkYSpkaWdpdF9BICsgKDEtbGFtYmRhKSpkaWdpdF9CCgpvdXRwdXRfaW50ZXJwb2xhdGlvbiA9IGRlY29kZShtb2RlbDIsbGF0ZW50X2ludGVycG9sYXRpb24pCgoKcGFyKG1hciA9IGMoMCwwLDAsMCkgKyAxLG1mcm93PWMoMSwzKSkKcGxvdF9kaWdpdChkaWdpdF9BKQpwbG90X2RpZ2l0KGFzLnZlY3RvcihvdXRwdXRfaW50ZXJwb2xhdGlvbikpCnBsb3RfZGlnaXQoZGlnaXRfQikKCgpwYXIobWFyID0gYygwLDAsMCwwKSArIDEsbWZyb3c9YygxLDMpKQpwbG90X2RpZ2l0KGRpZ2l0X0EpCnBsb3RfZGlnaXQoYXMudmVjdG9yKHJvdWdodF9pbnRlcnBvbGF0aW9uKSkKcGxvdF9kaWdpdChkaWdpdF9CKQoKYGBgCgoKCiMgUHJhY3RpY2UgYW5kIElsbHVzdHJhdGlvbiBpbiBNYWNoaW5lIExlYXJuaW5nCgoKIyMgd2l0aCBSIGNvZGUKLSBUaGUgUiBjb2RlIHVzZWQgZm9yIHRoaXMgdHV0b3JpYWwgaXMgW1Jjb2RlX3Vuc3VwZXJ2aXNlZF9sZWFybmluZy5SXSgvUmNvZGVfdW5zdXBlcnZpc2VkX2xlYXJuaW5nLlIpIAotIFRoZSBSIGNvZGUgdXNlZCBmb3IgdGhlIGJvb2sgW01hdGhlbWF0aWNhbCBFbmdpbmVlcmluZyBvZiBEZWVwIExlYXJuaW5nXShodHRwczovL2RlZXBsZWFybmluZ21hdGgub3JnLykgaXMgYXZhaWxhYmxlIG9uIFtHaXRIdWIgcmVwb10oaHR0cHM6Ly9naXRodWIuY29tL3lvbmluYXphcmF0aHkvTWF0aGVtYXRpY2FsRW5naW5lZXJpbmdEZWVwTGVhcm5pbmcpCgojIyB3aXRoIFB5dGhvbiBjb2RlIAoKLSBbVW5zdXBlcnZpc2VkIGxlYXJuaW5nIFByYWN0aWNlXShodHRwczovL2NvbGFiLnJlc2VhcmNoLmdvb2dsZS5jb20vZHJpdmUvMUFjYUxqcVVHYlhzS3V2MEw5Qmx5V3JfWFpUdVZoM1dpP3VzcD1zaGFyaW5nI3Njcm9sbFRvPUF4WUZDVnVFTWZKQykgKHZpYSBnb29nbGUgY29sbGFiKQoKIyBDaGFsbGVuZ2UgcHJhY3RpY2U6IHByZWRpY3Rpb24gdXNpbmcgUENBCgo8ZGl2IGNsYXNzID0gIm9yYW5nZSI+Cl9JbiB0aGlzIGNoYWxsZW5nZSwgd2Ugd2lsbCB1c2UgYW4gdW5zdXBlcnZpc2VkIG1ldGhvZCAoUHJpbmNpcGFsIENvbXBvbmVudCBBbmFseXNpcykgaW4gY29tYmluYXRpb24gd2l0aCBhIHN1cGVydmlzZWQgbWV0aG9kICgqKlNpZ21vaWQgbW9kZWwqKikgdG8gcGVyZm9ybSBhIGNsYXNzaWZpY2F0aW9uIHRhc2suIFRoaXMgYXBwcm9hY2ggcmVkdWNlcyBkYXRhIGRpbWVuc2lvbmFsaXR5IHRvIHJldGFpbiB0aGUgbW9zdCBpbXBvcnRhbnQgaW5mb3JtYXRpb24gYmVmb3JlIHRyYWluaW5nIGEgY2xhc3NpZmllci4gV2Ugd2lsbCB3b3JrIG9uIHRoZSBicmVhc3QgY2FuY2VyIGRhdGFzZXQuXyAqKlRoZSBtYWluIHN0ZXBzOioqCgoKCi0xLiBEYXRhIFByZXBhcmF0aW9uCgogICAgLSBMb2FkIHRoZSBkYXRhc2V0IGFuZCBzcGxpdCBpdCBpbnRvIHRyYWluaW5nIGFuZCB0ZXN0aW5nIHNldHMuCiAgICAtIFNlcGFyYXRlIHRoZSBmZWF0dXJlIGNvbHVtbnMgZnJvbSB0aGUgdGFyZ2V0IHZhcmlhYmxlIGluIGJvdGggc2V0cy4KICAgIAotMi4gRGltZW5zaW9uYWxpdHkgUmVkdWN0aW9uIHdpdGggUENBCgogICAgLSBTdGFuZGFyZGl6ZSB0aGUgZmVhdHVyZSBkYXRhLCB0aGVuIGFwcGx5IFBDQSB0byByZWR1Y2UgZGltZW5zaW9uYWxpdHkuCiAgICAtIFRyYW5zZm9ybSBib3RoIHRoZSB0cmFpbmluZyBhbmQgdGVzdCBzZXRzIHVzaW5nIHRoZSB0cmFpbmVkIFBDQSBtb2RlbC4KICAgIAotMy4gTW9kZWwgVHJhaW5pbmcKCiAgICAtIFRyYWluIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWxzIG9uIHRoZSBQQ0EtdHJhbnNmb3JtZWQgdHJhaW5pbmcgZGF0YQogICAgLSBVc2UgZGlmZmVyZW50IG51bWJlcnMgb2YgcHJpbmNpcGFsIGNvbXBvbmVudHMuCiAgICAKLTQuIE1vZGVsIEV2YWx1YXRpb24KCiAgICAtIEV2YWx1YXRlIGVhY2ggbW9kZWwgb24gdGhlIFBDQS10cmFuc2Zvcm1lZCB0ZXN0IHNldCB1c2luZyBhY2N1cmFjeSAKICAgIC0gUHJvdmlkZSBjb25mdXNpb24gbWF0cmljZXMgdG8gZGV0ZXJtaW5lIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjb21wb25lbnRzLgo8L2Rpdj4gCgojIyMgU29sdXRpb24KCltQeXRob24gY29kZSBzb2x1dGlvbl0oaHR0cHM6Ly9jb2xhYi5yZXNlYXJjaC5nb29nbGUuY29tL2RyaXZlLzFRdm9iYUNnUXBzS3BCcTBRTDctanJHbjFxTEM3VlhMaCNzY3JvbGxUbz1JYk5fWTlfN05XbEMpCgpbUiBjb2RlIHNvbHV0aW9uXShNYWNoaW5lTGVhcm5pbmcvU09MVVRJT05fcHJhY3RpY2VfUENBX3ByZWRpY3Rpb24uaHRtbCkK